左上角到右下角最小路径

---

题目描述

给定一个由非负整数填充的m x n的二维数组，现在要从二维数组的左上角走到右下角，请找出路径上的所有数字之和最小的路径。
注意：你每次只能向下或向右移动。

解题思路

与之前找路径条数的问题不同，这次要求找出”最短“路径。这就需要找到每次的最短路径了（这不废话吗>_>）之前求路径条数时，需要知道 每个临时终点 左和上浅蓝色位置的条数，然后做和。同样求最短路径也是从这两个浅蓝色位置入手（因为每次只能向下或向右运动，红色位置接受的数据只能由左或上）

比较两个浅蓝色位置的路径，选取最小值再加上当前位置数值即为最短路径，即为所求。

下面请康康代码，再理解一下吧！

代码

class Solution
{
public:
    int minPathSum(vector<vector<int> > &grid)
    {
        int rows = grid.size();
        int cols = grid[0].size();
        vector<vector<int> > dp(rows, vector<int>(cols, 0));
        
        for (int i = 0; i < rows; i++)
            for (int j = 0; j < cols; j++)
            {
                if (i * j != 0) // 第一行和第一列特殊
                {
                	dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + grid[i][j];
                }
                else if (i  == 0) // 第一行
                    dp[i][j] = dp[i][j - 1] + grid[i][j];
                else if (j == 0) // 第一列
                    dp[i][j] = dp[i - 1][j] + grid[i][j];
            }
        return dp[rows-1][cols-1];
    }
};

一维数组

class Solution
{
public:
    int minPathSum (vector<vector<int> > &grid)
    {
        int rows = grid.size();
        int cols = grid[0].size();
        
        vector<int> dp(cols, 0);
        
        for (int i = 0; i < rows; i++)
            for (int j = 0; j < cols; j++)
            {
                if (i * j != 0)
                    dp[j] = min(dp[j], dp[j - 1]) + grid[i][j];
                else if (i == 0)
                    dp[j] = dp[j - 1] + grid[i][j];
                else if (j == 0)
                    dp[j] = dp[j] + grid[i][j];
            }
        return dp[cols - 1];
    }
};

参考链接：

https://www.nowcoder.com/questionTerminal/23462ed010024fcabb7dbd3df57c715e?f=discussion