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

题目主要信息:

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

举一反三：

学习完本题的思路你可以解决如下题目：

BM67.不同路径的数目(一)

方法：动态规划（推荐使用）

知识点：动态规划

动态规划算法的基本思想是：将待求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解；对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。动态规划算法将问题的解决方案视为一系列决策的结果

思路：

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

具体做法：

• 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)$的位置就是到右下角的最短路径和。

图示：

Java实现代码：

import java.util.*;
public class Solution {
    public int minPathSum (int[][] matrix) {
        int n = matrix.length;
        //因为n,m均大于等于1
        int m = matrix[0].length;  
        //dp[i][j]表示以当前i，j位置为终点的最短路径长度
        int[][] dp = new int[n + 1][m + 1];
        dp[0][0] = matrix[0][0];
        //处理第一列
        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];
    }
}

C++实现代码：

class Solution {
public:
    int minPathSum(vector<vector<int> >& matrix) {
        int n = matrix.size();
        //因为n,m均大于等于1
        int m = matrix[0].size();  
        //dp[i][j]表示以当前i，j位置为终点的最短路径长度
        vector<vector<int> > dp(n + 1, vector<int>(m + 1, 0));
        dp[0][0] = matrix[0][0];
        //处理第一列
        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];
    }
};

Python代码实现：

class Solution:
    def minPathSum(self , matrix: List[List[int]]) -> int:
        n = len(matrix)
        #因为n,m均大于等于1
        m = len(matrix[0])  
        #dp[i][j]表示以当前i，j位置为终点的最短路径长度
        dp = [[0] * (m + 1) for i in range(n + 1)]
        dp[0][0] = matrix[0][0] 
        #处理第一列
        for i in range(1, n): 
            dp[i][0] = matrix[i][0] + dp[i - 1][0]
        #处理第一行
        for j in range(1, m): 
            dp[0][j] = matrix[0][j] + dp[0][j - 1]
        #其他按照公式来
        for i in range(1, n):  
            for j in range(1, m):
                if dp[i - 1][j] > dp[i][j - 1]:
                    dp[i][j] = matrix[i][j] + dp[i][j - 1]
                else:
                    dp[i][j] = matrix[i][j] + dp[i - 1][j]
        return dp[n - 1][m - 1]

复杂度分析：

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