114.最小路径和
题目
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例 1：
- 输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
- 输出：7
- 解释：因为路径 1→3→1→1→1 的总和最小。
示例 2：
- 输入：grid = [[1,2,3],[4,5,6]]
- 输出：12
思路: 动态规划
我们想知道从左上角到右下角的最小路径和，但我们可以先解决更小的问题：到达每个格子的最小路径和是多少？
因为只能向右或向下走，所以到达格子 (i,j) 只有两种可能:
- 从上方 (i-1, j) 下来
- 从左方 (i, j-1) 过来
因此，到达 (i,j) 的最小路径和 = 格子本身的值 + 到达上方和左方格子中较小的路径和。
状态定义
设 dp[i][j] 表示从左上角到达格子 (i,j) 的最小路径和。
状态转移
dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
边界条件
- 第一行（i=0）：只能从左方过来，所以 dp[0][j] = dp[0][j-1] + grid[0][j]。
- 第一列（j=0）：只能从上方过来，所以 dp[i][0] = dp[i-1][0] + grid[i][0]。
- 起点 dp[0][0] = grid[0][0]。
class Solution {
fun minPathSum(grid: Array<IntArray>): Int {
val m = grid.size
val n = grid[0].size
val dp = Array(m) { IntArray(n) }
dp[0][0] = grid[0][0]
// 第一行
for (j in 1 until n) {
dp[0][j] = dp[0][j - 1] + grid[0][j]
}
// 第一列
for (i in 1 until m) {
dp[i][0] = dp[i - 1][0] + grid[i][0]
}
// 其余格子
for (i in 1 until m) {
for (j in 1 until n) {
dp[i][j] = grid[i][j] + minOf(dp[i - 1][j], dp[i][j - 1])
}
}
return dp[m - 1][n - 1]
}
}
空间优化
因为 dp[i][j] 只依赖当前行和上一行的值，所以可以用一维数组 dp 来滚动更新，将空间复杂度降到 O(n)。
具体做法：
- 初始化 dp[0] = grid[0][0]。
- 先处理第一行：dp[j] = dp[j-1] + grid[0][j]。
- 然后从第二行开始，对于每一行：
- 第一个元素：dp[0] = dp[0] + grid[i][0]（dp[0] 此时是上一行的第一列值）。
- 后续元素：dp[j] = grid[i][j] + min(dp[j], dp[j-1])，其中 dp[j] 是上一行的值，dp[j-1] 是当前行已更新的左邻值。
复杂度
- 时间复杂度: O(m × n)
- 空间复杂度: 二维DP是O(m × n)，一维DP是O(n)
- 邮箱 ：charon.chui@gmail.com
- Good Luck!