hot100 -- 16.多维动态规划

1.不同路径

问题：

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

方法1：二维动态规划

def uniquePaths(m, n):grid = [[1 for i in range(n)] for j in range(m)]for i in range(1, m):for j in range(1, n):grid[i][j] = grid[i-1][j] + grid[i][j-1]return grid[-1][-1]

方法2：空间优化 -- 逐行迭代

每次运算，上一行的数据已由dp数组保留下来，相当于只用加左边数据即可（存储降维）

# 方法2：空间优化 -- 逐行迭代
# 每次运算，上一行的数据已由dp数组保留下来，相当于只用加左边数据即可（存储降维）
def uniquePaths(m, n):dp = [1] * nfor i in range(1, m):for j in range(1, n):dp[j] += dp[j-1]return dp[-1]

2.最小路径和

问题：

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

方法1：二维动态规划（二维dp数组）

# 方法1：二维动态规划（二维dp数组）
def minPathSum(grid):dp = [[1 for i in range(len(grid[0]))] for j in range(len(grid))]# 首行首列初始化：dp[0][0] = grid[0][0]for i in range(1, len(grid)):dp[i][0] = dp[i-1][0] + grid[i][0]for j in range(1, len(grid[0])):dp[0][j] = dp[0][j-1] + grid[0][j]for i in range(1, len(grid)):for j in range(1, len(grid[0])):dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]return dp[-1][-1]

方法2：空间优化（一维dp数组）

# 方法2：空间优化（一维dp数组）
def minPathSum(grid):dp = [1 for _ in range(len(grid[0]))]# 首行初始化dp[0] = grid[0][0]for j in range(1, len(grid[0])):dp[j] = dp[j-1] + grid[0][j]# 逐行运算for i in range(1, len(grid)):dp[0] += grid[i][0]                             # 首列初始化for j in range(1, len(grid[0])):dp[j] = min(dp[j], dp[j-1]) + grid[i][j]    # min(上方, 左方) + 当前元素值return dp[-1]

方法3：空间再优化（原地替换）

# 方法3：空间再优化（原地替换）
def minPathSum(grid):# 首行首列初始化for i in range(1, len(grid)):grid[i][0] += grid[i-1][0]for j in range(1, len(grid[0])):grid[0][j] += grid[0][j-1]for i in range(1, len(grid)):for j in range(1, len(grid[0])):grid[i][j] = min(grid[i-1][j], grid[i][j-1]) + grid[i][j]   # 原地替换return grid[-1][-1]