动态规划

核心概念

动态规划的特点是通过以下方式系统地解决问题优化：

将问题分解为重叠的子问题
只计算每个子问题一次并存储结果
重复使用这些结果来构建更大问题的解决方案

动态规划的效率来自于避免了重新计算已经计算过的结果。当问题包含许多重叠的子问题时，这尤其强大。

来源：[docs/chapter_dynamic_programming/intro_to_dynamic_programming.md:1-15]

DP 问题的关键特征

动态规划问题通常具备三个主要特征：

1. 重叠子问题

问题中需要多次解决同一个子问题。

在上图中，请注意 fib(3) 和 fib(2) 被计算了多次——这些是重叠子问题。

2. 最优子结构

当一个问题的最优解可以从其子问题的最优解构造出来时，该问题就具有最优子结构。

例如，在最小爬楼梯问题中，到达第 i 阶台阶的最小成本是

dp[i] = min(dp[i-1], dp[i-2]) + cost[i]

这个方程直接从较小子问题的最优解构建最优解。

3. 无后效性（记忆化）

子问题的解仅取决于当前状态，而与如何达到该状态无关。此属性确保一旦我们解决了子问题，其解决方案将保持有效，无论未来的决定如何。

当问题由于额外的约束而失去此属性时，我们通常需要扩展状态定义来恢复它。

来源：[docs/chapter_dynamic_programming/dp_problem_features.md:1-101]

动态规划的方法

暴力递归解法

我们首先将问题递归地表达出来，将其分解为更小的自身版本。

由于重叠子问题的重复计算，这种方法会导致指数级的时间复杂度。

示例（爬楼梯问题）

来源：[docs/chapter_dynamic_programming/intro_to_dynamic_programming.md:21-53]

记忆化（自顶向下）

在记忆化方法中，我们维护一个已计算结果的缓存。

在计算子问题之前，检查结果是否已在缓存中。
如果找到，则返回缓存的结果。
否则，计算结果并将其存储在缓存中。

示例（带记忆化的爬楼梯）

来源：[docs/chapter_dynamic_programming/intro_to_dynamic_programming.md:59-74]

制表法（自底向上）

制表法从最小的子问题开始向上构建解决方案。

定义一个表（数组）来存储子问题的解。
初始化基本情况。
通过从较小到较大的子问题迭代地填充表。

示例（带制表法的爬楼梯）

来源：[docs/chapter_dynamic_programming/intro_to_dynamic_programming.md:76-90]

空间优化

许多 DP 问题只需要有限的先前状态窗口即可计算当前状态。这使得我们可以通过仅存储必要的状态来优化空间使用。

来源：[docs/chapter_dynamic_programming/intro_to_dynamic_programming.md:100-108]

问题解决框架

在处理动态规划问题时，请遵循以下步骤：

1. 识别问题类型

通过检查以下几点来确定问题是否适合动态规划范式：

重叠子问题
最优子结构
具有优化目标的决策树结构

2. 定义状态和子问题

确定完全描述问题给定阶段的变量。
定义 DP 表中的每个条目代表什么。

3. 建立状态转移

确定如何从先前状态计算当前状态。
将其表示为递推关系或状态转移方程。

4. 确定基本情况

定义问题的最简单实例。
使用这些值初始化 DP 表。

5. 确定计算顺序

确保在计算某个状态时，其所有依赖的状态都已计算。
通常遵循状态依赖图的拓扑顺序。

来源：[docs/chapter_dynamic_programming/dp_solution_pipeline.md:1-32]

经典的 DP 问题

背包问题

0-1 背包

在这个问题中，给定 n 个具有重量和价值的物品，我们需要在不超过重量限制的情况下最大化价值。

状态定义：dp[i][w] = 使用前 i 个物品，重量限制为 w 的最大价值

状态转移：如果 w >= wgt[i-1]，则 dp[i][w] = max(dp[i-1][w], dp[i-1][w-wgt[i-1]] + val[i-1])

来源：[docs/chapter_dynamic_programming/knapsack_problem.md:1-36]

无界背包

一种物品可以选择多次的变体。

状态转移：如果 w >= wgt[i-1]，则 dp[i][w] = max(dp[i-1][w], dp[i][w-wgt[i-1]] + val[i-1])

与 0-1 背包的关键区别在于，选择一个物品后，您仍然可以选择同一个物品。

来源：[docs/chapter_dynamic_programming/unbounded_knapsack_problem.md:1-40]

路径问题

最小路径和

给定一个每个单元格都有成本的网格，找到从左上角到右下角总成本最小的路径。

状态定义：dp[i][j] = 到达单元格 (i,j) 的最小成本

状态转移：dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

来源：[docs/chapter_dynamic_programming/dp_solution_pipeline.md:34-90]

字符串问题

编辑距离

衡量将一个字符串转换为另一个字符串所需的最少操作次数（插入、删除、替换）。

状态定义：dp[i][j] = 将字符串 1 的前 i 个字符转换为字符串 2 的前 j 个字符所需的最少编辑次数

状态转移

如果字符匹配：dp[i][j] = dp[i-1][j-1]
否则：dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

来源：[docs/chapter_dynamic_programming/edit_distance_problem.md:1-52]

硬币找零问题

最少硬币数

找出找特定金额所需的最小硬币数。

状态定义：dp[i][a] = 使用前 i 种硬币找金额 a 所需的最少硬币数

状态转移：dp[i][a] = min(dp[i-1][a], dp[i][a-coins[i-1]] + 1)

硬币组合数

计算使用给定硬币找特定金额的不同方法数。

状态定义：dp[i][a] = 使用前 i 种硬币找金额 a 的方法数

状态转移：dp[i][a] = dp[i-1][a] + dp[i][a-coins[i-1]]

来源：[docs/chapter_dynamic_programming/unbounded_knapsack_problem.md:70-206]

与其他算法的比较

动态规划 vs. 分治算法

两者都将问题分解为更小的子问题。
分治算法：子问题是独立的。
动态规划：子问题是重叠的。

动态规划 vs. 贪心算法

两者都解决优化问题。
贪心算法：在不重新考虑的情况下做出局部最优选择。
动态规划：考虑所有可能性并找到全局最优解。

动态规划 vs. 回溯法

两者都可以使用带有状态跟踪的递归。
回溯法：通过剪枝探索所有可能性。
动态规划：侧重于通过记忆化进行优化。

来源：[docs/chapter_dynamic_programming/summary.md:1-9]

空间优化技术

通过观察我们只需要有限的先前状态窗口，许多 DP 问题都可以进行空间优化。

降维

对于每个状态仅取决于前一行的二维 DP 问题。

示例转换

双行优化：只保留当前行和上一行。
单行优化：使用单个数组并仔细遍历。

对于 0-1 背包：使用反向迭代以防止覆盖所需值。对于无界背包：使用正向迭代，因为我们希望重用更新后的值。

来源：[docs/chapter_dynamic_programming/knapsack_problem.md:135-168], [docs/chapter_dynamic_programming/unbounded_knapsack_problem.md:40-67]

常见陷阱和最佳实践

状态定义问题：确保您的状态定义捕获了所有相关信息。
基本情况错误：不正确地设置基本情况可能导致结果错误。
迭代顺序问题：确保计算顺序符合状态依赖关系。
次优的空间使用：寻找减少空间复杂度的机会。
遗漏约束：仔细识别可能影响状态转移的约束。

来源：[docs/chapter_dynamic_programming/dp_problem_features.md:52-101]

时间和空间复杂度分析

大多数 DP 解决方案具有：

时间复杂度：O(状态数 × 每个状态的时间)
空间复杂度：O(状态数)

对于优化场景：

带有记忆化的自顶向下：如果并非所有状态都必需，则空间复杂度可能更好。
带有空间优化的自底向上：通常可以将空间复杂度降低到 O(k)，其中 k 远小于状态数。

来源：[docs/chapter_dynamic_programming/summary.md:1-24]