算法:最小路径和【动态规划】
程序员文章站
2022-07-12 12:09:01
...
最小路径和
给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。
说明:每次只能向下或者向右移动一步。
示例:
输入: [ [1,3,1], [1,5,1], [4,2,1] ]
输出: 7
解释: 因为路径 1→3→1→1→1的总和最小。
题目分析:
- 矩阵最上角到右下角最小路径
- 每次只能向下或者向右移动一步(若没有方向限制,需要考虑递归 参考:格子里的整数)
- 利用动态规划:构建dp,用来存储最小路径,dp[i][j]表示从左上角走到(i,j)的最小路径。
- 则有:dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
- 考虑优化:可以将dp数组压缩为一维数据
# dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
def dpMinPathSum(grid): # dp解法
# initial
dp = [[0] * len(grid[0]) for _ in range(len(grid)) ]
dp[0][0] = grid[0][0]
for i in range(1, len(dp[0])):
dp[0][i] = dp[0][i-1] + grid[0][i]
for i in range(1, len(dp)):
dp[i][0] = dp[i-1][0] + grid[i][0]
# struct dp
for i in range(1, len(dp)):
for j in range(1, len(dp[0])):
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
return dp[-1][-1]
def opt_dp(grid): # dp优化解法
dp = [0] * len(grid[0])
dp[0] = grid[0][0]
for i in range(1, len(grid[0])):
dp[i] = dp[i-1] + grid[0][i]
for i in range(1, len(grid)):
dp[0] += grid[i][0] # 每次需初始化dp[0]
for j in range(1, len(grid[0])):
dp[j] = min(dp[j-1], dp[j]) + grid[i][j]
return dp[-1]
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
# return dpMinPathSum(grid)
return opt_dp(grid)
上一篇: 模块
下一篇: 动态规划--左上角到右下角的最大收益问题