动态规划

相关源文件

• assets/drawio/169.majority-element.drawio
• assets/problems/169.majority-element.png
• assets/problems/240.search-a-2-d-matrix-ii.png
• assets/problems/887.super-egg-drop-1.png
• assets/problems/887.super-egg-drop-2.png
• problems/1104.path-in-zigzag-labelled-binary-tree.md
• problems/139.word-break.md
• problems/198.house-robber.md
• problems/226.invert-binary-tree.md
• problems/230.kth-smallest-element-in-a-bst.md
• problems/232.implement-queue-using-stacks.md
• problems/240.search-a-2-d-matrix-ii.md
• problems/322.coin-change.md
• problems/416.partition-equal-subset-sum.md
• problems/518.coin-change-2.md
• problems/53.maximum-sum-subarray-cn.md
• problems/715.range-module.md
• problems/887.super-egg-drop.md
• thinkings/dynamic-programming.md
• thinkings/tree.md

本页记录了我们在代码库中用于解决各种算法问题的动态规划方法和技术。动态规划是一种解决优化问题的方法，通过将问题分解为更简单的子问题，并利用这些子问题的解来构建原问题的解。

有关动态规划中使用的二叉树等特定数据结构的更多信息，请参阅 树与图。

动态规划简介

动态规划是一种借用自其他领域的思想。它涉及将问题分解为阶段，在这些阶段之间进行转换以达到目标。由于每一步通常有多个可能的转换，因此必须做出关于走哪条路径的决策。

动态规划旨在找到一个最优解，其中

1. 阶段可以相互转换（这是“动态”的部分）
2. 必须选择转换以达到最优解（这是“规划”的部分）

来源： thinkings/dynamic-programming.md4-21

何时使用动态规划

当问题具有以下特征时，动态规划尤其有用：

1. 最优子结构 - 最优解可以由其子问题的最优解构成
2. 重叠子问题 - 同一个子问题被多次解决

如果没有动态规划，解决具有这些特征的问题通常会导致由于重复计算而产生的指数级时间复杂度。

来源： thinkings/dynamic-programming.md174-191 thinkings/dynamic-programming.md135-146

动态规划的核心组成部分

每个动态规划方法都包含三个基本要素：

1. 状态定义

状态定义是动态规划中最关键的部分。它涉及到如何表示问题在不同阶段的状态以及需要跟踪哪些信息。正确的状态定义对于开发高效的解决方案至关重要。

例如，在许多字符串问题中，状态可能是 dp[i]，表示字符串前 i 个字符的某个属性。对于涉及两个字符串的问题，状态可能是 dp[i][j]，表示字符串 1 的前 i 个字符和字符串 2 的前 j 个字符的属性。

来源： thinkings/dynamic-programming.md239-252

2. 状态转移方程

状态转移方程是显示如何从一个状态转移到另一个状态的公式。它定义了不同状态之间的关系，对于计算每个状态的值至关重要。

例如，在斐波那契数列问题中，转移方程将是

dp[i] = dp[i-1] + dp[i-2]

来源： thinkings/dynamic-programming.md419-432 problems/322.coin-change.md95-101

3. 基本情况

基本情况（或初始状态）定义了最简单子问题的起始值。这些是构建所有其他状态的基础。

对于斐波那契数列

dp[0] = 0
dp[1] = 1

来源： thinkings/dynamic-programming.md398-416

实现方法

有两种两种主要的方法来实现动态规划解决方案：

自顶向下方法（记忆化）

自顶向下方法使用带有记忆化的递归。它从原始问题开始，将其分解为子问题，缓存结果以避免重复计算。

来源： thinkings/dynamic-programming.md154-166

自底向上方法（制表）

自底向上方法从最简单的情况开始，构建子问题解的表格，然后逐步向上计算到原始问题。

来源： thinkings/dynamic-programming.md617-649

空间优化技术

许多动态规划解决方案可以通过仅存储当前计算所需的状态来优化空间。

例如，在斐波那契数列中，我们只需要前两个值来计算下一个值。

来源： thinkings/dynamic-programming.md630-649 problems/198.house-robber.md82-93

常见的 DP 问题类型

动态规划可以应用于各种类型的问题：

序列问题

涉及数组、字符串或序列的问题，其中解决方案取决于按特定顺序处理元素。

例如：最大子数组和 problems/53.maximum-sum-subarray-cn.md

来源： problems/53.maximum-sum-subarray-cn.md110-129

背包问题

涉及从具有不同价值和约束条件的项目集合中进行选择的问题。

例如：硬币找零 problems/322.coin-change.md

来源： problems/322.coin-change.md210-221

基于网格的问题

涉及在网格或矩阵上进行遍历或计算的问题。

区间问题

涉及区间的问题，通常需要不同的状态定义方法。

来源： thinkings/dynamic-programming.md685-702

状态压缩

状态空间很大且需要被压缩的问题。

来源： thinkings/dynamic-programming.md703-706

数位 DP

涉及数字的位数及其属性的问题。

来源： thinkings/dynamic-programming.md707-711

示例：找零问题

让我们以硬币找零问题为例，作为动态规划的完整示例。

问题：给定不同面额的硬币和一个总金额，找出凑成该金额所需的最少硬币数。

步骤 1：定义状态

• dp[i] = 凑成金额 i 所需的最少硬币数

步骤 2：状态转移方程

• 对于每个硬币面额 coin
  • dp[i] = min(dp[i], dp[i-coin] + 1) 如果 i-coin >= 0

步骤 3：基本情况

• dp[0] = 0 (凑成金额 0 需要 0 枚硬币)
• 将所有其他值初始化为 amount+1 (表示“不可能”)

步骤 4：解决方案

如果 dp[amount] 小于 amount+1，则答案是 dp[amount]，否则为 -1

来源： problems/322.coin-change.md94-101 problems/322.coin-change.md209-221

对比 DP 方法：记忆化与制表

方面	记忆化（自顶向下）	制表（自底向上）
方法	带缓存的递归	填充表格的迭代
计算方式	按需（惰性）	全面（积极）
实现	通常更容易实现	有时实现起来更复杂
堆栈使用	使用递归堆栈	无递归堆栈
空间优化	难以优化空间	通常允许空间优化
子问题	仅解决必要的子问题	解决指定范围内的所有子问题

来源： thinkings/dynamic-programming.md658-675

何时选择动态规划

当以下情况时使用动态规划：

1. 问题要求优化（最小/最大）或计数可能性
2. 问题表现出重叠子问题
3. 问题具有最优子结构（最优解包含子问题的最优解）
4. 递归解会因重复计算而导致指数级时间复杂度

来源： thinkings/dynamic-programming.md202-216

常见错误和挑战

1. 状态定义不正确：动态规划中最常见的错误是状态定义不当。
2. 基本情况缺失：忘记或错误地设置基本情况。
3. 状态转移方程错误：开发了不正确的状态关系。
4. 忽略状态依赖性：未考虑正确的计算顺序。
5. 空间效率低下：在可能的情况下未能优化空间。

来源： thinkings/dynamic-programming.md730-731

练习题

以下是一些推荐的练习题，以帮助您掌握动态规划：

1. 硬币找零 (322)
2. 打家劫舍 (198)
3. 单词拆分 (139)
4. 硬币找零 2 (518)
5. 分割等和子集 (416)

来源：thinkings/dynamic-programming.md915-928