【LeetCode 刷题】动态规划(1)-基础

此博客为《代码随想录》动态规划章节的学习笔记，主要内容为动态规划基础的相关题目解析。

文章目录

• 509. 斐波那契数
• 70. 爬楼梯
• 746. 使用最小花费爬楼梯
• 62. 不同路径
• 63. 不同路径 II
• 343. 整数拆分
• 96. 不同的二叉搜索树

509. 斐波那契数

题目链接

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

• 状态定义：dp[i] 的值代表 斐波那契数列第 i 个数字
• 转移方程：dp[i] = dp[i-1] + dp[i−2]
• 初始状态：dp[0] = 0，dp[1] = 1，即初始化前两个数字
• 遍历顺序：从前到后
• 返回值：dp[n]，即斐波那契数列的第 n 个数字。

70. 爬楼梯

题目链接

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

• 状态定义：dp[i] 的值代表 到达第 i 阶楼梯有多少种方案
• 初始值：dp[0] = 0，dp[1] = 1，到达第 0、1 个阶梯都仅有一种方案
• 其余与上题相同

746. 使用最小花费爬楼梯

题目链接

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

• 状态定义：dp[i] 的值代表 到达第 i 阶楼梯的最少花费
• 初始值：dp[0] = 0，dp[1] = 0，可以直接从下标为 0、1 的阶梯开始爬，因此最小花费为 0
• 转移方程：dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])

62. 不同路径

题目链接

class Solution:def uniquePaths(self, m: int, n: int) -> int:dp = [[0 for _ in range(n)] for _ in range(m)]for i in range(m):dp[i][0] = 1for i in range(n):dp[0][i] = 1for i in range(1, m):for j in range(1, n):dp[i][j] = dp[i-1][j] + dp[i][j-1]return dp[m-1][n-1]

• 状态定义：dp[i][j] 的值代表 到达下标第 (i, j) 网格有多少种路径
• 初始值：第一行、第一列 均为1
• 转移方程：dp[i][j] = dp[i-1][j] + dp[i][j-1]

另一种 dp 设置思路

class Solution:def uniquePaths(self, m: int, n: int) -> int:dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]dp[0][1] = 1for i in range(1, m + 1):for j in range(1, n + 1):dp[i][j] = dp[i-1][j] + dp[i][j-1]return dp[m][n]

• 状态定义：dp[i][j] 的值代表 到达下标第 (i - 1, j - 1) 网格有多少种路径，即外围添加了一圈
• 初始值：dp[0][1] = 1 或者 dp[1][0] = 1，仅用于确保结果正确，无具体逻辑意义，其他额外添加的外围网格，均保持默认的初始化 0 （省去了大量的初始赋值）
• 返回值：dp[m][n]

63. 不同路径 II

题目链接

class Solution:def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:m, n = len(obstacleGrid), len(obstacleGrid[0])dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]dp[0][1] = 1for i in range(1, m + 1):for j in range(1, n + 1):if obstacleGrid[i-1][j-1] == 1:dp[i][j] = 0else:dp[i][j] = dp[i-1][j] + dp[i][j-1]return dp[m][n]

• 与上题第二种思路基本相同，仅状态转移时如果遇到障碍直接赋值为 0
• 注意：dp 数组与原始的网格的坐标之间存在 1 的偏差，因此判断的网格点为 obstacleGrid[i-1][j-1]

343. 整数拆分

题目链接

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

• 状态定义：dp[i] 的值代表 数 i 划分后得到的最大乘积
• 初始化：dp[1] = 1 （跳过 dp[0]）
• 状态转移： d p [ i ] = max ⁡ 1 ≤ j < i { max ⁡ ( j × ( i − j ) , j × d p [ i − j ] ) } dp[i]=\max_{1≤j<i}\{\max(j×(i−j),j×dp[i−j])\} dp[i]=max1≤j<i​{max(j×(i−j),j×dp[i−j])}
  • 将 i 拆分成 j 和 i − j 的和，且 i − j 不再拆分成多个正整数：i * (i−j)
  • 将 i 拆分成 j 和 i − j 的和，且 i − j 继续拆分成多个正整数：j * dp[i−j]

数学方法

class Solution:def integerBreak(self, n: int) -> int:if n <= 3: return n - 1a, b = n // 3, n % 3if b == 0: return int(math.pow(3, a))if b == 1: return int(math.pow(3, a - 1) * 4)return int(math.pow(3, a) * 2)

• 尽可能拆分成 3
  • n % 3 == 0，全部拆成 3
  • n % 3 == 1，用一个 3 搭配 1，拆成 2 * 2，其他全部拆成 3
  • n % 3 == 2，拆一个 2，其他全部拆成 3

96. 不同的二叉搜索树

题目链接

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

• 总节点为 n 的二叉搜索树，左右子树的节点数可能为（左，右）：(0, n - 1)…(j, n - 1 - j)…(n - 1, 0)