题解 | #矩阵的最小路径和#

题目主要信息:

• 给定一个矩阵，从矩阵左上角到右下角，每次只能向下或者向右
• 从左上角到右下角路径上经过的所有数字之和为路径和，求该路径和的最小值
• 矩阵不为空，每个元素值都为非负数

具体思路:

最朴素的解法莫过于枚举所有的路径，然后求和，找出其中最大值。但是像这种有状态值可以转移的问题，我们可以尝试用动态规划。

• step 1：我们可以构造一个与矩阵同样大小的二维辅助数组，其中$dp[i][j]dp[i][j]$表示以$(i,j)(i,j)$位置为终点的最短路径和，则$dp[0][0]=matrix[0][0]dp[0][0]\; =\; matrix[0][0]$。
• step 2：很容易知道第一行与第一列，只能分别向右或向下，没有第二种选择，因此第一行只能由其左边的累加，第一列只能由其上面的累加。
• step 3：边缘状态构造好以后，遍历矩阵，补全矩阵中每个位置的dp数组值：如果当前的位置是$(i\mathrm{，}j)(i，j)$，上一步要么是$(i-1,j)(i-1,j)$往下，要么就是$(i,j-1)(i,j-1)$往右，那么取其中较小值与当前位置的值相加就是到当前位置的最小路径和，因此状态转移公式为$dp[i][j]=min(dp[i-1][j],dp[i][j-1])+matrix[i][j]dp[i][j]\; =\; min(dp[i-1][j],\; dp[i][j-1])\; +\; matrix[i][j]$。
• step 4：最后移动到$(n-1,m-1)(n-1,m-1)$的位置就是到右下角的最短路径和。

转移过程可参考如下图示：

代码实现:

class Solution {
public:
    int minPathSum(vector<vector<int> >& matrix) {
        int n = matrix.size();
        int m = matrix[0].size();  //因为n,m均大于等于1
        vector<vector<int> > dp(n + 1, vector<int>(m + 1, 0));
        dp[0][0] = matrix[0][0];//dp[i][j]表示以当前i，j位置为终点的最短路径长度
        for(int i = 1; i < n; i++)//处理第一列
            dp[i][0] = matrix[i][0] + dp[i - 1][0];
        for(int j = 1; j < m; j++)//处理第一行
            dp[0][j] = matrix[0][j] + dp[0][j - 1];
        for(int i = 1; i < n; i++){ //其他按照公式来
          for(int j = 1; j < m; j++){
              dp[i][j] = matrix[i][j] + (dp[i - 1][j] > dp[i][j - 1] ? dp[i][j - 1] : dp[i - 1][j]);
          }
      }
       return dp[n - 1][m - 1];
    }
};

复杂度分析：

• 时间复杂度：$O(mn)O(mn)$，单独遍历矩阵的一行一列，然后遍历整个矩阵
• 空间复杂度：$O(mn)O(mn)$，辅助矩阵dp的大小