leetcode 链接：最小路径和

题目

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

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

示例：

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

输入：grid = [[1,2,3],[4,5,6]]
输出：12

解答 & 代码

动态规划：

• 设置一个 dp 数组，dp[row][col] 代表从 (0, 0) 走到 (row, col) 位置的最小路径和
• 状态转移方程：dp[row][col] = min(dp[row - 1][col], dp[row][col - 1]) + grid[row][col]

• 初始化：

  • dp[0][0] = grid[0][0]
  • 第一行 dp[0][col] = grid[0][col] + dp[0][col - 1]

  • 第一列 dp[row][0] = grid[row][0] + dp[row - 1][0]

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

    执行结果： ``` 执行结果：通过

执行用时：8 ms, 在所有 C++ 提交中击败了 90.47% 的用户 内存消耗：9.8 MB, 在所有 C++ 提交中击败了 40.66% 的用户

改进：<br />可以将 `dp` 数组压缩为一维数组，只存储一行（或只存储一列也行，或取行、列的较小值）
```cpp
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int rows = grid.size();
        if(rows <= 0)
            return -1;
        int cols = grid[0].size();
        if(cols <= 0)
            return -1;

        vector<int> dp(cols, 0);
        dp[0] = grid[0][0];
        for(int col = 1; col < cols; ++col)
            dp[col] = grid[0][col] + dp[col - 1];
        for(int row = 1; row < rows; ++row)
        {
            dp[0] += grid[row][0];
            for(int col = 1; col < cols; ++col)
                dp[col] = min(dp[col], dp[col - 1]) + grid[row][col];
        }

        return dp[cols - 1];
    }
};

执行结果：通过

执行用时：8 ms, 在所有 C++ 提交中击败了 90.47% 的用户
内存消耗：9.4 MB, 在所有 C++ 提交中击败了 84.48% 的用户