LintCode110 最小路径和

问题描述

给定一个只含非负整数的m*n网格，找到一条从左上角到右下角的可以使数字和最小的路径。

（每次只能向下或向左移动一步）

样例 1:
	输入:  [[1,3,1],[1,5,1],[4,2,1]]
	输出: 7
	
	样例解释：
	路线为： 1 -> 3 -> 1 -> 1 -> 1。
	
样例 2:
	输入:  [[1,3,2]]
	输出:  6
	
	解释:  
	路线是： 1 -> 3 -> 2

问题分析

典型的动态规划问题。每个位置的最短路径value=当前位置的路径pos(i,j)+MIN（上面节点的路径(i-1,j)，左边节点的路径(i,j-1)），即每个节点的路径值是当前得的路径值加上来的路径（左方或者上方）的最小值。如样例1中，（1，1）的值为5，那么来路的路径最小值为2（（0，0）-->（1，0））,所以到达（1，1）的最小路径值为7（1+1+5）。

需要分三种情况：

1.当节点处在网格第一行时（i=0），value(0,j)=pos(i,j)+pos(i,j-1)；

2.当节点处在网格第一列时（j=0），value(i,0)=pos(i,j)+pos(i-1,j)；

3.当节点不在第一行和第一列时（i!=0&&j!=0），value(i,j)=pos(i,j)+min(pos(i,j-1) , pos(i-1,j))；

代码

class Solution {
public:
    /**
     * @param grid: a list of lists of integers
     * @return: An integer, minimizes the sum of all numbers along its path
     */
    int minPathSum(vector<vector<int>> &grid) {
        // write your code here
    vector<vector<int>> arr=grid;
    if(arr.empty()){
        return 0;
    }
    int n=arr.size();
    int m=arr[0].size();
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(i==0&&j==0){
            }
            else if(i==0&&j!=0){
                arr[i][j]=arr[i][j-1]+arr[i][j];
            }
            else if(i!=0&&j==0){
                arr[i][j]=arr[i-1][j]+arr[i][j];
            }
            else{
                int a=min(arr[i-1][j],arr[i][j-1]);
                arr[i][j]=a+arr[i][j];
            }
        }
    }
    return arr[n-1][m-1];
        
    }
};

测试代码如下

#include <iostream>
#include <vector>
using namespace std;

int main(){
    vector<vector<int>> vec;
    //m*n m行n列
    int m;
    int n;
    cin>>m>>n;
    for(int i=0;i<m;i++){
        vector<int> temp;
        for(int j=0;j<n;j++){
            int a;
            cin>>a;
            temp.push_back(a);
        }
        vec.push_back(temp);
        temp.clear();
    }
    vector<vector<int>> arr=vec;
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(i==0&&j==0){
            }
            else if(i==0&&j!=0){
                arr[i][j]=arr[i][j-1]+arr[i][j];
            }
            else if(i!=0&&j==0){
                arr[i][j]=arr[i-1][j]+arr[i][j];
            }
            else{
                int a=min(arr[i-1][j],arr[i][j-1]);
                arr[i][j]=a+vec[i][j];
            }
        }

    }
    cout<<"--------"<<endl;
    for(int i=0;i<m;i++){
        for(int k:arr[i]){
            cout<<k<<" ";
        }
        cout<<endl;
    }

}

LintCode110 最小路径和

原文：https://www.cnblogs.com/fazhou/p/12733743.html