当前位置：首页 > article >正文

从二维到一维：动态规划矩阵问题的优化之道

article 2024/11/17 20:24:32

动态规划中的矩阵问题是非常经典的应用场景，比如最小路径和问题。这类问题很自然地可以想到使用二维 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 数组表示最后一行的状态，状态转移方程如下：

遍历最后一行
因为最后一行没有下方格子，所以每个位置的状态只需要考虑右方状态：
dp[j] = grid[i][j] + dp[j+1]
遍历最后一列
因为最后一列没有右方格子，所以每个位置的状态只需要考虑下方状态（即当前 dp[j]）：
dp[j] = grid[i][j] + dp[j]
遍历其他位置
对于矩阵中其他位置，需要同时参考右方和下方状态：
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:
                    continue
                elif 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]