64 最小路径和-动态规划

题目描述：
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例:
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。

方法1 使用二维空间的动态规划
主要思路：
（1）到达当前点的路径只能是从左边，或上边的点移动过来，则若要知道到达当前点的最小路径和，只需要在可能的路径点中，既左边和上边两个点，选择一个较小值，用这个较小值加上当前结点的值，既为到达当前点的最小路径和；
（2）直观的，声明一个和原数组大小相同的数组，存储到达各个当前点的最小路径和，对于第一列和第一行可以单独的进行初始化；

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        //处理特殊的情形
        if(grid.empty())
            return 0;
         //获得数组的行和列
        int rows=grid.size();
        int cols=grid[0].size();
        //定义一个和路径数组相同大小的数组，存储到达各个点的最小路径和
        vector<vector<int>> dp(rows,vector<int>(cols,0));
        //对第一个点进行初始化
        dp[0][0]=grid[0][0];
        //对第一列进行初始化
        for(int i=1;i<cols;++i){
            dp[0][i]=dp[0][i-1]+grid[0][i];
        }
        //对第一行进行初始化
        for(int i=1;i<rows;++i){
            dp[i][0]=dp[i-1][0]+grid[i][0];
        }
        //遍历数组
        for(int i=1;i<rows;++i){
            for(int j=1;j<cols;++j){
                //当前点的最小路径和，是从之前的所有可能路径中，选出一个最小的路径和，加上当前结点的值
                dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j];
            }
        }
        //返回最终结果
        return dp[rows-1][cols-1];
    }
};

方法2 使用一维空间的动态规划
主要思路：
这里的主要思路和二维的基本上一样，只不过使用了一维的数组存储中间变量

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        //处理特殊情形
        if(grid.empty())
            return 0;
        //获得路径数组的行数和列数
        int rows=grid.size();
        int cols=grid[0].size();
        //定义存储路径和的一维数组
        vector<int> dp(cols,0);
        //根据路径的第一行，对数组进行初始化
        dp[0]=grid[0][0];
        for(int i=1;i<cols;++i){
            dp[i]=grid[0][i]+dp[i-1];
        }
        //从路径数组的第二行开始遍历
        for(int i=1;i<rows;++i){
            for(int j=0;j<cols;++j){
                //单独处理每一行的第一个元素，因为到达这个位置，只能从上边的一个点
                if(j==0){
                    dp[j]=dp[j]+grid[i][j];
                }
                //根据左边和上边点，选出路径最小值，加上当前点的值
                else{
                    dp[j]=min(dp[j],dp[j-1])+grid[i][j];
                }
            }
        }
        //返回结果
        return dp[cols-1];
    }
};