64. 最小路径和

Posted on Edited on In Views: Word count in article: 671 Reading time ≈ 1 mins.

64. 最小路径和

题目链接：64. 最小路径和

题目描述

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

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

核心思考：动态规划（记忆化搜索）

本题是典型的矩阵动态规划问题。由于机器人只能向右或向下移动，到达任一位置 (i, j) 的最小路径和，取决于到达其上方位置 (i-1, j) 和左方位置 (i, j-1) 的最小路径和。

  1. 状态定义：设 dfs(i, j) 为从起点 (0, 0) 到达坐标 (i, j) 的最小路径和。
  2. 转移方程：到达 (i, j) 的代价为当前格子的值加上前一步的最小代价。
    dfs(i, j) = min(dfs(i-1, j), dfs(i, j-1)) + grid[i][j]
  3. 递归边界：
    • 起点：i == 0 且 j == 0 时，直接返回 grid[0][0]。
    • 越界处理：如果 i < 0 或 j < 0，代表该路径非法，返回无穷大 inf，确保在 min 运算中被过滤。
  4. 性能保障：使用 Python 内置的 @cache 装饰器实现记忆化搜索。每个格子的最小路径和只会被计算一次，从而将搜索的时间复杂度从指数级优化为线性级别。

解题思路 (Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        
        @cache
        def dfs(i, j):
            # 边界处理：越界返回无穷大
            if i < 0 or j < 0:
                return inf
            
            # 起点：返回初始值
            if i == 0 and j == 0:
                return grid[i][j]

            # 状态转移：当前值 + 来自上方或左方的最小值
            return min(dfs(i - 1, j), dfs(i, j - 1)) + grid[i][j]

        return dfs(m - 1, n - 1)

复杂度分析

  • 时间复杂度：$O(M \times N)$，其中 $M$ 和 $N$ 分别为网格的长和宽。每个状态仅需映射计算一次。
  • 空间复杂度：$O(M \times N)$。用于缓存递归结果的存储开销以及最大 $M+N$ 层次的递归栈深度。

ACM 模式

本节提供 ACM 竞赛风格的完整可运行代码，包含输入输出处理。

输入格式：

1
2
3
4
5
m n
a11 a12 a13 ... a1n
a21 a22 a23 ... a2n
...
am1 am2 am3 ... amn

第一行输入矩阵的行数 m 和列数 n，随后输入 m 行 n 列的矩阵元素。

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import sys

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
    m, n = len(grid), len(grid[0])

            @cache
            def dfs(i, j):
                # 边界处理：越界返回无穷大
                if i < 0 or j < 0:
                    return inf

                # 起点：返回初始值
                if i == 0 and j == 0:
                    return grid[i][j]

                # 状态转移：当前值 + 来自上方或左方的最小值
                return min(dfs(i - 1, j), dfs(i, j - 1)) + grid[i][j]

            return dfs(m - 1, n - 1)

def main():
    data = sys.stdin.read().strip().split()
    m, n = int(data[0]), int(data[1])
    idx = 2
    matrix = []
    for i in range(m):
        row = list(map(int, data[idx:idx+n]))
        matrix.append(row)
        idx += n

    sol = Solution()
    result = sol.minPathSum(matrix)
    print(result)

if __name__ == "__main__":
    main()

运行示例：

1
echo -e "3 3\n1 2 3\n4 5 6\n7 8 9" | python solution.py