学习网站建设的网站2021年最为成功的营销案例

动态规划中的矩阵问题是非常经典的应用场景，比如最小路径和问题。这类问题很自然地可以想到使用二维 dp 数组来求解。
我们定义：
dp[i][j]
表示从矩阵的第 i行第 j列到右下角的最小路径和。

基本解法

求解过程从右下角开始，向左上角遍历，每次选择当前位置右方和下方的最小路径和来更新当前格子的状态。
状态转移方程为：
dp[i][j] = grid[i][j] + min(dp[i+1][j], dp[i][j+1])

这种方法思路清晰，容易实现。然而，空间复杂度为 O(NM)，有优化的空间。

优化空间复杂度

通过观察可以发现，每次计算某个位置时，只需要用到当前位置的右方和下方的状态值。因此，我们可以用一个 一维数组 dp 来代替二维数组，从而将空间复杂度优化为 O(N)。

优化方法

我们仍然从矩阵右下角开始倒序遍历。假设当前 dp 数组表示最后一行的状态，状态转移方程如下：

1. 遍历最后一行
   因为最后一行没有下方格子，所以每个位置的状态只需要考虑右方状态：
   dp[j] = grid[i][j] + dp[j+1]

2. 遍历最后一列
   因为最后一列没有右方格子，所以每个位置的状态只需要考虑下方状态（即当前 dp[j]）：
   dp[j] = grid[i][j] + dp[j]

3. 遍历其他位置
   对于矩阵中其他位置，需要同时参考右方和下方状态：
   dp[j] = grid[i][j] + min(dp[j], dp[j+1])

这样，dp 数组在整个计算过程中始终保持当前位置右方和下方的最小路径和。

实现代码

def minPathSum(self, grid: List[List[int]]) -> int:rows = len(grid)cols = len(grid[0])dp = grid[rows-1]for i in range(rows - 1, -1, -1):for j in range(cols - 1, -1, -1):if i == rows - 1 and j == cols - 1:continueelif i == rows - 1:dp[j] += dp[j+1]elif j == cols - 1:dp[j] += grid[i][j]else:dp[j] = min(dp[j],dp[j+1])+grid[i][j]return dp[0]

类似题目

不同路径
不同路径II
三角形最小路径和