网站建设运营外包,建设网站的企业费用,海阳有没有做企业网站的,搭建公司动态规划中的矩阵问题是非常经典的应用场景#xff0c;比如最小路径和问题。这类问题很自然地可以想到使用二维 dp 数组来求解。 我们定义#xff1a; dp[i][j] 表示从矩阵的第 i行第 j列到右下角的最小路径和。
基本解法
求解过程从右下角开始#xff0c;向左上角遍历比如最小路径和问题。这类问题很自然地可以想到使用二维 dp 数组来求解。 我们定义 dp[i][j] 表示从矩阵的第 i行第 j列到右下角的最小路径和。
基本解法
求解过程从右下角开始向左上角遍历每次选择当前位置右方和下方的最小路径和来更新当前格子的状态。 状态转移方程为 dp[i][j] grid[i][j] min(dp[i1][j], dp[i][j1]) 这种方法思路清晰容易实现。然而空间复杂度为 O(NM)有优化的空间。 优化空间复杂度
通过观察可以发现每次计算某个位置时只需要用到当前位置的右方和下方的状态值。因此我们可以用一个 一维数组 dp 来代替二维数组从而将空间复杂度优化为 O(N)。
优化方法
我们仍然从矩阵右下角开始倒序遍历。假设当前 dp 数组表示最后一行的状态状态转移方程如下 遍历最后一行 因为最后一行没有下方格子所以每个位置的状态只需要考虑右方状态 dp[j] grid[i][j] dp[j1] 遍历最后一列 因为最后一列没有右方格子所以每个位置的状态只需要考虑下方状态即当前 dp[j] dp[j] grid[i][j] dp[j] 遍历其他位置 对于矩阵中其他位置需要同时参考右方和下方状态 dp[j] grid[i][j] min(dp[j], dp[j1])
这样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[j1]elif j cols - 1:dp[j] grid[i][j]else:dp[j] min(dp[j],dp[j1])grid[i][j]return dp[0]类似题目
不同路径 不同路径II 三角形最小路径和
