动态规划

相关源文件

• README.md

目的与范围

本文档全面介绍了 leetcode-master 仓库中实现的动态规划（DP）方法。动态规划是一种优化技术，通过将复杂问题分解为更简单的重叠子问题，并仅解决每个子问题一次，然后存储解决方案以供将来参考，从而解决复杂问题。

本节涵盖了动态规划的理论基础、实现策略和常见问题模式。有关贪心算法等相关算法方法，请参见贪心算法；有关基于动态规划概念的更高级实现，请参见图论。

动态规划基础

动态规划通过结合子问题的解决方案来解决问题。它适用于问题具有以下特征的情况：

1. 最优子结构：问题的最优解包含其子问题的最优解
2. 重叠子问题：相同的子问题被多次解决

两种关键实现方法

来源：README.md（第282-362行）

自顶向下 (记忆化)

• 缓存结果的递归方法
• 从大到小解决问题实例
• 通常使用哈希表或数组进行缓存

自底向上 (制表)

• 使用表格（数组）的迭代方法
• 从小到大构建问题解决方案
• 通常比记忆化更节省空间

DP问题分类

该仓库将动态规划问题组织成几个类别，每个类别都具有独特的特点和解决方案模式

来源：README.md（第286-362行）

基本DP问题

这些问题介绍了基本的DP概念，具有相对简单的状态转换

问题	描述	状态定义	状态转移
509. 斐波那契数	计算第n个斐波那契数	dp[i] = 第i个斐波那契数	dp[i] = dp[i-1] + dp[i-2]
70. 爬楼梯	计算爬n级楼梯有多少种方法（每次可以走1步或2步）	dp[i] = 到达第i级楼梯的方法数	dp[i] = dp[i-1] + dp[i-2]
746. 使用最小花费爬楼梯	爬楼梯的最小花费	dp[i] = 到达第i级楼梯的最小花费	dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
62. 不同路径	计算网格中的独特路径数	dp[i][j] = 到达单元格 (i,j) 的路径数	dp[i][j] = dp[i-1][j] + dp[i][j-1]

来源：README.md（第287-296行）

背包问题

背包问题是动态规划问题中一个重要的子集，其中必须优化选择具有重量和价值的物品。

来源：README.md（第298-321行）

0-1 背包

• 每个物品只能使用一次（0次或1次）
• 状态通常定义为：dp[i][j] = 使用前i个物品和容量j所能获得的最大价值
• 状态转移：dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i])
• 通常可以优化为一维数组：dp[j] = max(dp[j], dp[j-weight[i]] + value[i])

完全背包

• 每个物品可以使用无限次
• 状态转移的关键区别：dp[j] = max(dp[j], dp[j-weight[i]] + value[i])
• 物品循环在外层，容量循环在内层（与0-1背包不同）

多重背包

• 每个物品有特定的使用限制
• 可以通过复制物品转换为0-1背包

打家劫舍系列

打家劫舍问题涉及在约束条件下做出最优选择决策

问题	描述	状态定义	关键思路
198. 打家劫舍	抢劫非相邻房屋以获得最大金额	dp[i] = 考虑前i个房屋后能获得的最大金额	dp[i] = max(dp[i-2] + nums[i], dp[i-1])
213. 打家劫舍 II	相同，但房屋围成一圈	两种情况：抢劫房屋0到n-2，或抢劫房屋1到n-1	处理环形约束
337. 打家劫舍 III	抢劫二叉树，其中父子节点不能同时被抢劫	dp[node][0/1] = 不抢劫/抢劫节点时能获得的最大金额	每个节点具有两种状态的树形DP

来源：README.md（第323-327行）

股票交易问题

股票交易问题涉及寻找最优买卖点以最大化利润

来源：README.md（第329-342行）

状态表示

• 通常使用dp[i][j]，其中
  • i 代表天数
  • j 代表状态（例如，0 = 未持有股票，1 = 持有股票）
• 更复杂的问题会增加额外的状态，例如交易次数或冷却期状态

状态转换

对于基本问题

• dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])（未持有，要么保持未持有，要么卖出）
• dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])（持有，要么保持持有，要么买入）

子序列问题

子序列问题涉及识别序列中的模式

问题类型	描述	主要示例
最长递增子序列	找到元素按升序排列的最长子序列	300. LIS（最长递增子序列）, 674. 最长连续递增子序列
最长公共子序列	找到两个序列的最长公共子序列	1143. LCS（最长公共子序列）, 1035. 不相交的线
最大和子序列	找到和最大的子序列	53. 最大子数组和
编辑距离	将一个字符串转换为另一个字符串的操作	72. 编辑距离, 583. 两个字符串的删除操作
回文问题	查找或构造回文子序列	647. 回文子串, 516. 最长回文子序列

来源：README.md（第344-362行）

子序列问题的常见方法

1. 定义状态：通常dp[i]或dp[i][j]表示前i个或i,j个元素的最优解
2. 分析添加新元素如何影响状态
3. 根据新元素是否包含在最优解中来定义状态转移
4. 仔细处理基本情况

动态规划模式总结

模式	关键特点	问题示例
线性DP	一维状态数组	斐波那契数，爬楼梯
网格DP	遵循网格结构的二维状态数组	不同路径，最小路径和
背包问题	具有重量/价值的选择问题	0-1 背包，完全背包
状态机	具有状态转移的独立状态	股票交易问题
子序列	在序列中查找模式	LIS（最长递增子序列），LCS（最长公共子序列），编辑距离
区间动态规划	区间上的最优解	戳气球，矩阵链乘法

来源：README.md（第286-362行）

实现策略与优化

空间优化

许多DP问题可以降低其空间复杂度

• 二维到一维数组（例如，背包问题）
• 一维到常数空间（例如，斐波那契数列）
• 使用滚动数组（只保留最后几个状态）

初始化

• 始终仔细处理基本情况
• 识别允许正确状态转移的初始状态
• 考虑无效或边界情况

遍历顺序

• 确保满足依赖关系（在需要子问题之前计算它们）
• 对于二维问题，遍历顺序可能至关重要（例如，背包问题的变体）
• 有些问题需要特定的遍历模式（对角线、逆序等）

结论

动态规划是一种强大的技术，通过将优化问题分解为重叠的子问题来解决它们。leetcode-master 仓库提供了一种结构化的学习DP方法，将问题分类为不同的模式，并提供分步解决方案，以帮助内化这些概念。

有关仓库中涵盖的所有动态规划问题的完整探索，请参阅 README.md（第282-362行）中列出的资源，其中涵盖了50多个根据类型和难度精心选择的动态规划问题。