动态规划 _规划

一身转战三千里，一剑曾百万师。这篇文章主要讲述动态规划相关的知识，希望能为你提供帮助。
1. 斐波那契数列509. 斐波那契数

斐波那契数（通常用 F(n) 表示）形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1 给定 n ，请计算 F(n) 。示例 1：输入：n = 2 输出：1 解释：F(2) = F(1) + F(0) = 1 + 0 = 1 示例 2：输入：n = 3 输出：2 解释：F(3) = F(2) + F(1) = 1 + 1 = 2 示例 3：输入：n = 4 输出：3 解释：F(4) = F(3) + F(2) = 2 + 1 = 3 提示：0 < = n < = 30

题解：

class Solution: def fib(self, n: int) -> int: if n == 0: return 0if n == 1: return 1dp = [0] * (n + 1)# 定义 dp 数组 dp[0] = 0# 初始化 dp[1] = 1for i in range(2, n+1): dp[i] = dp[i - 1] + dp[i - 2]# 递推公式return dp[n]

2. 爬楼梯70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？示例 1：输入：n = 2 输出：2 解释：有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶示例 2：输入：n = 3 输出：3 解释：有三种方法可以爬到楼顶。 1. 1 阶 + 1 阶 + 1 阶 2. 1 阶 + 2 阶 3. 2 阶 + 1 阶提示：1 < = n < = 45

爬楼梯实质上也可以看作一个斐波拉契数列：

class Solution: def climbStairs(self, n: int) -> int: dp = [0] * (n+1) dp[0] = 1 dp[1] = 1 for i in range(2, n+1): dp[i] = dp[i-1] + dp[i-2]return dp[n]

【动态规划】类似题目剑指 Offer 10- II. 青蛙跳台阶问题：

class Solution: def numWays(self, n: int) -> int: if n == 0 or n == 1: return 1dp = [0] * (n + 1) dp[0] = 1# 0 个台阶有 1 种方法 dp[1] = 1# 1 个台阶有 1 种方法for i in range(2, n + 1): dp[i] = dp[i - 1] + dp[i - 2]return dp[n] % 1000000007

3. 不同路径62. 不同路径

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。问总共有多少条不同的路径？示例 1：输入：m = 3, n = 7 输出：28 示例 2：输入：m = 3, n = 2 输出：3 解释：从左上角开始，总共有 3 条路径可以到达右下角。 1. 向右 -> 向下 -> 向下 2. 向下 -> 向下 -> 向右 3. 向下 -> 向右 -> 向下示例 3：输入：m = 7, n = 3 输出：28 示例 4：输入：m = 3, n = 3 输出：6 提示：1 < = m, n < = 100 题目数据保证答案小于等于 2 * 109

题解一：

class Solution: def uniquePaths(self, m: int, n: int) -> int: dp = [[0 for i in range(n)] for j in range(m)]def diff_path(row, col):# 第一列的任意单元格，只有来自它上一个单元格过来的方法 for i in range(n): dp[0][i] = 1# 第一行的任意单元格，只有来自它前一个单元格过来的一种方法 for j in range(m): dp[j][0] = 1# 随意一个单元格有来自上或者左的两种路径，第一行、第一列已填充，不用继续填充 for i in range(1, row): for j in range(1, col): dp[i][j] = dp[i - 1][j] + dp[i][j - 1]# 返回最后一个单元格的位置 return dp[row - 1][col - 1]return diff_path(m, n)

题解二：（更容易理解）

class Solution: def uniquePaths(self, m: int, n: int) -> int: dp = [[0] * nfor i in range(m)]for row in range(m): for col in range(n): # 第一个格子只有一种方法 if row == 0 and col == 0: dp[row][col] = 1 elif col == 0: # 第一行的任意单元格，只有来自它前一个单元格过来的一种方法 dp[row][col] = dp[row-1][col] elif row == 0: # 第一列的任意单元格，只有来自它上一个单元格过来的方法 dp[row][col] = dp[row][col - 1] else: # 其他情况（中间）：任意一个单元格有来自其左或上两个方向的机器人 dp[row][col] = dp[row - 1][col] + dp[row][col - 1]return dp[m - 1][n - 1]

4. 不同路径 II63. 不同路径 II

示例 1：输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]] 输出：2 解释：3x3 网格的正中间有一个障碍物。从左上角到右下角一共有 2 条不同的路径： 1. 向右 -> 向右 -> 向下 -> 向下 2. 向下 -> 向下 -> 向右 -> 向右示例 2：输入：obstacleGrid = [[0,1],[0,0]] 输出：1 提示：m == obstacleGrid.length n == obstacleGrid[i].length 1 < = m, n < = 100 obstacleGrid[i][j] 为 0 或 1

题解：

class Solution: def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int: row = len(obstacleGrid) col = len(obstacleGrid[0])# 只有一个单元格，即一行一列时 if row == 1 and col == 1: if obstacleGrid[0][0] == 1: return 0 else: return 1dp = [[0] * col for i in range(row)]for i in range(row): for j in range(col): # 遇到阻碍，就跳过当前循环 if obstacleGrid[i][j] == 1: continueif i == 0 and j == 0: dp[i][j] = 1 elif i == 0: dp[i][j] = dp[i][j - 1] elif j == 0: dp[i][j] = dp[i - 1][j] else: dp[i][j] = dp[i][j - 1] + dp[i - 1][j]return dp[row - 1][col - 1]

5. 最小路径和64. 最小路径和

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。说明：每次只能向下或者向右移动一步。示例 1：输入：grid = [[1,3,1],[1,5,1],[4,2,1]] 输出：7 解释：因为路径 1→3→1→1→1 的总和最小。示例 2：输入：grid = [[1,2,3],[4,5,6]] 输出：12 提示：m == grid.length n == grid[i].length 1 < = m, n < = 200 0 < = grid[i][j] < = 100

题解：

class Solution: def minPathSum(self, grid: List[List[int]]) -> int: m, n = len(grid), len(grid[0])# 只有一个单元格时 if m == 1 and n == 1: return grid[0][0]dp = [[0] * n for i in range(m)]for i in range(m): for j in range(n):if i == 0: # 第一行，和 = 当前单元格数字 + 前一个单元格数字 dp[i][j] = dp[i][j - 1] + grid[i][j] elif j == 0: # 第一列，和 = 当前单元格数字 + 上一个单元格数字 dp[i][j] = dp[i - 1][j] + grid[i][j] else: # 中间单元格，和 = 当前单元格数字 + 上一个和前一个单元格中最小的数字 dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j]return dp[m-1][n-1]