题解 | 矩阵的最小路径和

1、解题思路

1. 动态规划： 定义 dp[i][j] 为从 (0, 0) 到 (i, j) 的最小路径和。递推关系： dp[i][j] = a[i][j] + min(dp[i-1][j], dp[i][j-1])。初始条件： dp[0][0] = a[0][0]。dp[i][0] = dp[i-1][0] + a[i][0]（只能向下走）。dp[0][j] = dp[0][j-1] + a[0][j]（只能向右走）。
2. 空间优化： 使用滚动数组优化空间，将空间复杂度从 O(n × m) 降为 O(m) 或 O(n)。

2、代码实现

C++

#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param matrix int整型vector<vector<>> the matrix
     * @return int整型
     */
    int minPathSum(vector<vector<int> >& matrix) {
        // write code here
        int n = matrix.size(), m = matrix[0].size();
        vector<vector<int>> dp(n, vector<int>(m, 0));
        dp[0][0] = matrix[0][0];

        for (int i = 1; i < n; ++i) { // 初始化第一列
            dp[i][0] = dp[i - 1][0] + matrix[i][0];
        }
        for (int j = 1; j < m; ++j) { // 初始化第一行
            dp[0][j] = dp[0][j - 1] + matrix[0][j];
        }

        for (int i = 1; i < n; ++i) {
            for (int j = 1; j < m; ++j) {
                dp[i][j] = matrix[i][j] + min(dp[i - 1][j], dp[i][j - 1]);
            }
        }

        return dp[n - 1][m - 1];
    }
};

进阶

#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param matrix int整型vector<vector<>> the matrix
     * @return int整型
     */
    int minPathSum(vector<vector<int> >& matrix) {
        // write code here
        int n = matrix.size(), m = matrix[0].size();
        vector<int> dp(m, 0);   // 空间 O(m)
        dp[0] = matrix[0][0];

        for (int j = 1; j < m; ++j) { // 初始化第一行
            dp[j] = dp[j - 1] + matrix[0][j];
        }

        for (int i = 1; i < n; ++i) {
            dp[0] += matrix[i][0];
            for (int j = 1; j < m; ++j) {
                dp[j] = matrix[i][j] + min(dp[j], dp[j - 1]);
            }
        }
        
        return dp[m - 1];
    }
};

Java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param matrix int整型二维数组 the matrix
     * @return int整型
     */
    public int minPathSum (int[][] matrix) {
        // write code here
        int n = matrix.length, m = matrix[0].length;
        int[][] dp = new int[n][m]; // 空间 O(n × m)
        dp[0][0] = matrix[0][0];
        for (int i = 1; i < n; ++i) { // 初始化第一列
            dp[i][0] = dp[i - 1][0] + matrix[i][0];
        }
        for (int j = 1; j < m; ++j) { // 初始化第一行
            dp[0][j] = dp[0][j - 1] + matrix[0][j];
        }
        for (int i = 1; i < n; ++i) { // 填充 dp 表格
            for (int j = 1; j < m; ++j) {
                dp[i][j] = matrix[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[n - 1][m - 1];
    }
}

Python

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param matrix int整型二维数组 the matrix
# @return int整型
#
class Solution:
    def minPathSum(self, matrix: List[List[int]]) -> int:
        # write code here
        n, m = len(matrix), len(matrix[0])
        dp = [[0] * m for _ in range(n)]  # 空间 O(n × m)
        dp[0][0] = matrix[0][0]
        for i in range(1, n):  # 初始化第一列
            dp[i][0] = dp[i - 1][0] + matrix[i][0]
        for j in range(1, m):  # 初始化第一行
            dp[0][j] = dp[0][j - 1] + matrix[0][j]
        for i in range(1, n):  # 填充 dp 表格
            for j in range(1, m):
                dp[i][j] = matrix[i][j] + min(dp[i - 1][j], dp[i][j - 1])
        return dp[n - 1][m - 1]

3、复杂度分析

• 时间复杂度：O(n × m)，其中 n 和 m 分别是矩阵的行数和列数。
• 空间复杂度：O(n × m)，用于存储 dp 表格。

进阶

• 时间复杂度：O(n × m)。
• 空间复杂度：O(m)，优化为一维数组。