动态规划入门指南

1. 公式
   观察依据

   阶乘的递推关系表示为$4! = 4 * 3!$、$3! = 3 * 2!$、$2! = 2 * 1!$和$1! = 1$。

2. 声音
   观察依据

   讲解者说明：要计算 factorial(n)，需先计算 factorial($n-1$)。

n!

非负整数 n 的阶乘，通过递归方式定义为$n! = n \cdot (n-1)!$，其基础情形为$1! = 1$（并隐含$0! = 1$，尽管未明确写出）。

非负整数

1. 公式
   观察依据

   树状图标注为 fib(7)、fib(6)、fib(5) 等，代表斐波那契数列。

2. 声音
   观察依据

   讲解者在展示斐波那契树时，提到了‘动态规划’这一术语的起源。

fib(n)

第 n 个斐波那契数通常由$fib(n) = fib(n-1) + fib(n-2)$定义，其基础情形为$fib(0)=0, fib(1)=1$。

非负整数

1. 公式
   观察依据

   屏幕上的公式显示为：`SHORTEST_PATH(SF, SD) = SHORTEST_PATH(SF, LA) + SHORTEST_PATH(LA, SD)`。

2. 声音
   观察依据

   讲述者称，整个问题可用这个函数来概括。

SHORTEST_PATH(A, B)

一种类似函数的记号，用于表示两座城市 A 与 B 之间的最短路径。

示例地图中的城市；SF 表示旧金山，LA 表示洛杉矶，SD 表示圣地亚哥。

1. 图示
   观察依据

   地图标注将旧金山、洛杉矶和圣地亚哥标为路径的起点、终点及途经的中间城市。

2. 公式
   观察依据

   所显示的公式中，SF、LA、SD 作为 SHORTEST_PATH 的参数。

SF, LA, SD

最短路径示例中使用的旧金山、洛杉矶和圣地亚哥的缩写。

路径示例中出现的城市名称。

1. 声音
   观察依据

   讲述者提到计算第五个斐波那契数。

2. 图示
   观察依据

   展示了一棵递归树，其根节点标记为5，重复出现的子树分别标记为2和3。

3. 字幕依据
   观察依据

   讲述者明确提到了像 fib(2) 和 fib(3) 这样的重复函数调用。

1. 视频未展示斐波那契数的正式递推公式；仅展示了递归树示例。

fib(n)

第 n 项斐波那契数的递归计算，通过函数调用树图示说明。

示例中使用非负整数下标；可见节点包括5、4、3、2、1、0。

1. 声音
   观察依据

   讲解某一问题何时可用动态规划求解时，主讲人反复提到“动态规划”一词。

2. 图示
   观察依据

   文氏图将“最优子结构”与“重叠子问题”的交集标注为“动态规划问题”。

DP

动态规划是一种求解具有最优子结构和重叠子问题性质的问题的方法。

算法设计与问题求解

1. 声音
   观察依据

   讲解者将动态规划定义为一种算法优化技术：它以递归方式将复杂问题分解为更小的、相互重叠的子问题，并利用这些子问题的解来构造原问题的解。

2. 公式
   观察依据

   阶乘示例展示了将$4!$逐步分解为$3!$，再分解为$2!$，最后分解为$1!$的过程。

动态规划是一种算法优化技术，它通过递归地将复杂问题分解为更小的、相互重叠的子问题，并组合这些子问题的解，从而构造出原问题的解。

1. 该问题可以被分解为若干更小的子问题。

2. 这些子问题存在重叠（同一个子问题被多次求解）。

3. 原问题的解可以通过子问题的解来构造。

1. 声音
   观察依据

   讲述者指出，动态规划问题的第一个条件是“最优子结构”：即问题可被划分为子问题，且其最优解可由这些子问题的最优解构造而成。

2. 图示
   观察依据

   维恩图中，“最优子结构”是定义“动态规划问题”的两个相交圆圈之一。

若一个问题的最优解能够高效地由其子问题的最优解构造出来，则该问题具有最优子结构。

1. 该问题可以被划分为若干子问题。

2. 主问题的最优解依赖于其子问题的最优解。

1. 动态规划的定义

1. 声音
   观察依据

   讲述者将第二个条件介绍为“子问题重叠”。

2. 图示
   观察依据

   维恩图中，“子问题重叠”是定义“动态规划问题”的另一个相交圆圈。

1. 视频在完整解释“子问题重叠”含义之前就中断了。

如果一个递归算法在求解某个问题时反复求解相同的子问题，而不是每次都生成新的子问题，则该问题具有重叠子问题。

1. 该问题可通过递归方式求解。

2. 相同的子问题在递归树中多次出现。

1. 动态规划的定义

1. 图示
   观察依据

   一张名为《动态规划问题的特征》的韦恩图，展示了“最优子结构”与“重叠子问题”，二者交集处标注为“动态规划问题”。

2. 声音
   观察依据

   讲述者首先介绍第一个概念——最优子结构，随后指出第二个特征是重叠子问题。

该片段将动态规划呈现为两种性质的交集：一个问题必须同时具备最优子结构和重叠子问题。韦恩图直观表明，这两个条件共同刻画了一个动态规划问题。

1. 用作对动态规划问题的入门式特征描述。

2. 该片段未就这两个性质之外的内容提供形式化证明或详尽列举。

1. 声音
   观察依据

   讲述者说：‘本质上，若一个整体问题的最优解可通过高效组合其子问题的最优解而构造出来，则该问题具有最优子结构。’

2. 图示
   观察依据

   地图示例将旧金山至圣地亚哥的路线在洛杉矶处划分为两条子路线。

3. 公式
   观察依据

   屏幕上显示等式 `SHORTEST_PATH(SF, SD) = SHORTEST_PATH(SF, LA) + SHORTEST_PATH(LA, SD)`。

最优子结构是指整个问题的最优解可以由各个更小子问题的最优解组合而成。在路线示例中，一旦已知旧金山→洛杉矶和洛杉矶→圣地亚哥这两段最短路径，它们拼接起来就构成了旧金山→圣地亚哥的最短路线。

1. 该示例假设整条路线经过洛杉矶。

2. 讲述者指出，在本例中，找出各段最短子路径即可保证得到整条路线的最短路径。

1. 动态规划问题的两个定义性特征

1. 声音
   观察依据

   讲述者说：‘至于第二个特征，我们有重叠子问题。’随后解释道，重复计算会出现在递归树中。

2. 图示
   观察依据

   斐波那契递归树展示了 fib(2) 和 fib(3) 对应的重复子树，以红色高亮显示。

3. 字幕依据
   观察依据

   屏幕文字包含‘重叠子问题’，并提及重复的函数调用。

当同一较小问题在递归过程中被多次求解时，便出现重叠子问题。斐波那契树通过展示诸如 fib(2) 和 fib(3) 等重复调用，使这一现象变得具体可感，从而导致冗余计算。

1. 借助斐波那契数列的朴素递归实现加以说明。

2. 该片段通过调用树中的重复现象来定义该术语，而非借助形式化定理。

1. 动态规划问题的两个定义性特征
2. 递归即函数自我调用，直至抵达基准情形

1. 声音
   观察依据

   讲述者称，递归本质上是一个函数反复调用自身，直至抵达基础情形。

2. 动画
   观察依据

   一个简单动画显示‘P’分叉为‘step’和另一个‘P’，持续向下重复，直至出现‘基础情形’。

1. 该片段仅对递归给出了简短的非正式解释，并未形式化地定义基准情形。

视频采用简化的动画来解释递归：问题 P 反复调用自身，每次执行一步，直至达到基准情形。这有助于观众理解为何重复的子调用可能产生重叠。

1. 此处仅为简要的概念性介绍，而非对递归的完整讲解。

1. 声音
   观察依据

   “那么它将表现出重叠子问题。”

2. 图示
   观察依据

   展示了一棵递归树，其中重复出现的子树被红色圆圈标出。

视频通过递归树示意图定义重叠子问题：递归分解的不同分支会再次访问相同的较小规模子问题；红色圆圈标记了重复出现的子树，直观表明同一子问题被多次求解。

1. 该问题正通过递归方式求解。

2. 递归分解会多次重新访问同一子问题。

1. 声音
   观察依据

   “若满足这两个条件，则动态规划可更高效地求解该问题。”

2. 图示
   观察依据

   文氏图将这两个条件命名为“最优子结构”与“重叠子问题”。

1. 第一个条件在此片段中并未完整说出，而是从后续的维恩图标签中识别得出。

该片段指出，若满足两个条件，动态规划便能更高效地解决该问题。后续图示将这两个条件明确标识为：最优子结构和重叠子问题。

1. 该问题满足最优子结构。

2. 该问题表现出重叠子问题。

1. 重叠子问题

1. 声音
   观察依据

   “因此在处理一个问题时，首先尝试看它能否用递归方法求解。”

2. 声音
   观察依据

   “为最好地判断这一点，请尝试看分治法是否适用于该问题。”

3. 声音
   观察依据

   “观察将问题分解为最简单的子问题后，是否最终能逐步构建出最优解。”

主讲人给出了一种实用检验方法：首先尝试用递归求解该问题，然后检查分治式的分解是否可行，再检查将问题拆分为最简单的子问题后，是否最终能逐步构建出最优解。若以上均可实现，主讲人表示此时可采用递归，并由此得知该问题可用动态规划求解。

1. 你正在判断一个问题是否适合采用动态规划。

1. 应用动态规划的两个条件

1. 图示
   观察依据

   标题：“动态规划问题的特征”。

2. 图示
   观察依据

   左侧圆圈：“最优子结构”；右侧圆圈：“重叠子问题”；交集部分：“动态规划问题”。

3. 声音
   观察依据

   “好的，以上就是判断一个问题能否用动态规划求解的两个主要特征。”

文氏图概括了判断一个问题能否用动态规划求解的两个主要特征：最优子结构与重叠子问题。它们的交集被标注为动态规划问题。

1. 用作动态规划适用条件的概念性总结。

1. 应用动态规划的两个条件
2. 重叠子问题

1. 声音
   观察依据

   “事实上，我归纳出五个值得关注的指标。”

2. 图示
   观察依据

   幻灯片标题：“5 动态规划指标”，其下列表项为1至5。

在总结完形式化特征之后，主讲人提出了五个用于实际识别动态规划问题的实用指标：序列化决策、贪心选择性质、状态转移、路径或数组、计数或最优化（最大化/最小化）。

1. 用作实践中识别动态规划问题的经验法则。

1. 动态规划问题的特征

1. 声音
   观察依据

   讲述者指出：‘一个问题属于动态规划问题，当且仅当它满足两个条件。’

2. 图示
   观察依据

   维恩图直观地将‘最优子结构’与‘重叠子问题’的交集表示为‘动态规划问题’。

一个问题属于动态规划问题，当且仅当它同时满足两个条件：最优子结构和重叠子问题。

1. 该问题可通过某种算法策略求解。

对所有问题而言，若其具备最优子结构和重叠子问题，则它就是一个动态规划问题。

1. 声音
   观察依据

   讲述者指出：如果我们找到了从旧金山到洛杉矶的最短路径，以及从洛杉矶到圣地亚哥的最短路径，那么就一定能得到从旧金山到圣地亚哥的整体最短路径。

2. 公式
   观察依据

   屏幕上显示的等式将整条最短路径等于两条较短路段路径之和。

1. 该片段并未证明这一保证为何成立，而是通过示例直接断言它。

在所呈现的示例中，若已知旧金山→洛杉矶的最短路径与洛杉矶→圣地亚哥的最短路径，则将二者拼接即可得到旧金山→圣地亚哥的最短路径。

1. 从旧金山到圣地亚哥的路径经过洛杉矶。

2. 每一段子路径均被选为其端点之间的最短路径。

针对视频中展示的这个特定三城市路径示例。

1. 声音
   观察依据

   讲述者说道：“这并不理想，而动态规划将帮助我们剔除所有正在重复进行的计算。”

2. 图示
   观察依据

   斐波那契递归树中重复出现的子树被标出，以凸显其中的冗余计算。

1. 该片段定性地说明了这一优势，并未提供复杂度分析。

动态规划有助于消除由重叠子问题所引发的重复计算。

1. 递归过程包含重复子问题，斐波那契树对此作了图示说明。

在所展示的斐波那契递归示例背景下。

1. 声音
   观察依据

   “若这两个条件均满足，则动态规划可更高效地求解该问题。”

1. 本片段在音频中并未完整复述这两个条件；后续图示中才为其命名。

如果满足这两个条件，那么动态规划就能更高效地解决该问题。

1. 该问题满足视频中讨论的两个条件。

对于当前讨论的问题，若这两个条件均成立，则动态规划更为高效。

1. 声音
   观察依据

   如果你能做到这一点，你就能判断是否可以应用递归；此时你就能确定无疑地知道，该问题可用动态规划求解。

1. 这是演讲者在视频中明确提出的蕴含关系；该片段并未提供形式化证明。

如果你能将问题逐层分解至最简单的子问题，并自底向上构建出最优解，那么你就可以应用递归；而演讲者指出，此时你就能确定无疑地知道，该问题可用动态规划求解。

1. 该问题可被递归地分解为最简单的子问题。

2. 这些子问题可被逐步构建出最优解。

对于正在检验的问题，若递归分解与自底向上构建均成功，则根据视频所述，动态规划适用。

1. 声音
   观察依据

   换句话说，如果你能用贪心算法解决一个问题，那么你也能用动态规划解决它。

1. 这是演讲者提出的一个启发式论断，并未在该片段中加以证明。

如果一个问题可以用贪心算法求解，那么它也可以用动态规划求解。

1. 该问题可用贪心算法求解。

适用于视频中所述具有贪心选择性质的问题。

1. 公式
   观察依据

   $4!$的逐步分解过程如下：$4! = 4 * 3!$、$3! = 3 * 2!$、$2! = 2 * 1!$、$1! = 1$。

2. 动画
   观察依据

   方框依次出现，展示递归调用过程，随后返回值逐步累积形成最终答案：$1 \rightarrow 2 \rightarrow 6 \rightarrow 24$。

1. 公式

   $$4! = 4 * 3!$$
   解释

   从求4的阶乘这一问题开始。

   步骤依据

   阶乘的定义。

   视频直接表达
2. 公式

   $$3! = 3 * 2!$$
   解释

   要求3!，我们需要先求2!。

   步骤依据

   阶乘的递归定义。

   视频直接表达
3. 公式

   $$2! = 2 * 1!$$
   解释

   要求2!，我们需要先求1!。

   步骤依据

   阶乘的递归定义。

   视频直接表达
4. 公式

   $$1! = 1$$
   解释

   到达基础情形。

   步骤依据

   阶乘基础情形的定义。

   视频直接表达
5. 公式

   $$2! = 2 * 1 = 2$$
   解释

   将1!代回2!的表达式中。

   步骤依据

   算术代入。

   视频直接表达
6. 公式

   $$3! = 3 * 2 = 6$$
   解释

   将2!代回3!的表达式中。

   步骤依据

   算术代入。

   视频直接表达
7. 公式

   $$4! = 4 * 6 = 24$$
   解释

   将3! 代回关于4! 的方程中。

   步骤依据

   算术代入。

   视频直接表达

递归分解与后续的逐步构建正确计算出$4! = 24$。

1. 声音
   观察依据

   讲述者解释道：由于高速公路途经洛杉矶，该问题可被划分为两个子问题。

2. 图示
   观察依据

   箭头在地图上标出了旧金山、洛杉矶和圣地亚哥，且路线在洛杉矶处被直观地分割开来。

3. 公式
   观察依据

   在口头分解之后，屏幕上出现方程：〔SHORTEST_PATH(SF, SD) = SHORTEST_PATH(SF, LA) + SHORTEST_PATH(LA, SD)〕。

1. 该推导基于具体示例，侧重直观理解，而非形式化证明。

1. 公式

   $$\text{Find the shortest path from San Francisco to San Diego.}$$
   解释

   原始问题被表述为地图上的路径查找任务。

   步骤依据

   由旁白和地图示例直接给出。

   视频直接表达
2. 公式

   $$\text{The route passes through Los Angeles.}$$
   解释

   旁白指出洛杉矶是高速公路路线上的中间点。

   步骤依据

   音频中明确说明，同时地图上高亮显示洛杉矶。

   视频直接表达
3. 公式

   $$\text{Split into } SF \to LA \text{ 且 } LA \to SD.$$
   解释

   整个行程被分解为两个较小的路径问题。

   步骤依据

   旁白明确描述为将问题划分为两个子问题。

   视频直接表达
4. 公式

   $$SHORTEST_PATH(SF, SD) = SHORTEST_PATH(SF, LA) + SHORTEST_PATH(LA, SD)$$
   解释

   最优的完整路径被写作两个最优子路径之和。

   步骤依据

   在屏幕上显示，并以该示例的函数形式进行口头总结。

   视频直接表达

该示例通过从子问题的最优解构造全局最优解，展示了最优子结构性质。

1. 图示
   观察依据

   以5为根节点的递归树展开为针对3和2的重复子树。

2. 声音
   观察依据

   旁白指出高亮区域代表重复工作，并点明存在如 fib(2) 和 fib(3) 这样的重复函数调用。

3. 字幕依据
   观察依据

   屏幕文字将 `FIB(2)` 和 `FIB(3)` 列为重复调用。

1. 视频并未在画面上明确写出递推式 `$F(n)=F(n-1)+F(n-2)$`；该式是从所展示的标准斐波那契递归树中推断得出的。

1. 公式

   $$\text{Start from the root call for the 5th Fibonacci number.}$$
   解释

   该树被引入为计算 fib(5) 所需的工作量。

   步骤依据

   旁白明确指出这是第五个斐波那契数的例子。

   视频直接表达
2. 公式

   $$\text{Expand recursively into smaller calls.}$$
   解释

   该树向下分叉，生成标有 4、3、2、1 和 0 的函数调用。

   步骤依据

   在递归树图示中可见。

   视频直接表达
3. 公式

   $$\text{Notice repeated subtrees for } fib(3) \text{ 且 } fib(2).$$
   解释

   相同的较小问题在不同分支中多次出现。

   步骤依据

   讲解者强调了重复计算，并点明了 fib(2) 和 fib(3)。

   视频直接表达
4. 公式

   $$\text{These repeats are overlapping subproblems.}$$
   解释

   重复出现的子树说明了朴素递归中冗余的重复计算。

   步骤依据

   由旁白和视觉高亮直接解释。

   视频直接表达

斐波那契示例通过可视化方式阐明了重叠子问题的含义，以及为何它推动了动态规划的引入。

1. 声音
   观察依据

   讲解顺序从重叠子问题出发，过渡到双条件检验，再尝试递归与分治法，最终得出动态规划适用性的结论。

2. 图示
   观察依据

   一棵递归树中用红色圆圈标出重复的子树，以此支持上述解释。

1. 公式

   $$$$
   解释

   视频首先指出递归树中存在重复的子树，并说明该问题具有重叠子问题性质。

   步骤依据

   在音频中直接陈述，并通过红色圆圈标出的重复分支加以展示。

   视频直接表达
2. 公式

   $$$$
   解释

   接着指出：若两个条件均满足，则动态规划能更高效地求解该问题。

   步骤依据

   在音频中直接陈述。

   视频直接表达
3. 公式

   $$$$
   解释

   随后，主讲人提出一个实用检验方法：尝试用递归方式求解该问题，并观察分治法是否可行。

   步骤依据

   音频中直接陈述。

   视频直接表达
4. 公式

   $$$$
   解释

   该测试通过提问来进一步明确：将问题分解为最简单的子问题，是否最终能逐步构建出最优解。

   步骤依据

   音频中直接陈述。

   视频直接表达
5. 公式

   $$$$
   解释

   最后，主讲人得出结论：如果这一点能够实现，那么就可以应用递归，并确认该问题可用动态规划求解。

   步骤依据

   音频中直接陈述。

   视频直接表达

该片段提供了一条直观路径：从识别重叠子问题和递归可分解性出发，最终推断出动态规划适用。

1. 图示
   观察依据

   维恩图，标题为“动态规划问题的特征”。

2. 声音
   观察依据

   “这两项是判断一个问题能否用动态规划求解的两个主要特征。”

1. 公式

   $$$$
   解释

   左侧集合标注为“最优子结构”。

   步骤依据

   图中可见。

   视频直接表达
2. 公式

   $$$$
   解释

   右侧集合标注为“重叠子问题”。

   步骤依据

   在图中可见。

   视频直接表达
3. 公式

   $$$$
   解释

   它们的交集被标记为“动态规划问题”。

   步骤依据

   在图中可见。

   视频直接表达
4. 公式

   $$$$
   解释

   旁白指出，这是决定一个问题能否用动态规划求解的两个主要特征。

   步骤依据

   音频中直接陈述。

   视频直接表达

视觉论证将动态规划问题概括为：恰好位于最优子结构与重叠子问题二者交集中的那些问题。

1. 公式
   观察依据

   该例题显式地计算了$4!$。

2. 动画
   观察依据

   图示方框展示了 factorial(4) 的递归调用及返回值。

使用递归方法计算4! 的值。

1. 对应的式子为：$n = 4$

2. 对应的式子为：$n! = n \cdot (n-1)!$

3. 对应的式子为：$1! = 1$

求4! 的数值。

1. 公式

   $$4! = 4 * 3!$$
   解释

   对 $n = 4$ 应用递归公式。

   步骤依据

   阶乘的定义。

   视频直接表达
2. 公式

   $$3! = 3 * 2!$$
   解释

   对 $n = 3$ 应用递归公式。

   步骤依据

   阶乘的定义。

   视频直接表达
3. 公式

   $$2! = 2 * 1!$$
   解释

   对 $n = 2$ 应用递归公式。

   步骤依据

   阶乘的定义。

   视频直接表达
4. 公式

   $$1! = 1$$
   解释

   到达基础情形。

   步骤依据

   阶乘的定义。

   视频直接表达
5. 公式

   $$2! = 2 * 1 = 2$$
   解释

   从基础情形返回，并计算 2!。

   步骤依据

   算术运算。

   视频直接表达
6. 公式

   $$3! = 3 * 2 = 6$$
   解释

   返回并计算 3!。

   步骤依据

   算术运算。

   视频直接表达
7. 公式

   $$4! = 4 * 6 = 24$$
   解释

   返回并计算4！。

   步骤依据

   算术运算。

   视频直接表达

对应的式子为：24

计算所得的值24与4！的标准数学结果一致。

1. 图示
   观察依据

   一棵大型树状图展示了计算 fib(7) 时的递归调用，突出显示了重复出现的节点，例如 fib(5)、fib(4) 等。

1. 该视频并未显式计算 fib(7) 的最终值，仅展示树状结构以说明子问题重叠现象。

在不使用记忆化的情况下，演示计算 fib(7) 所涉及的递归调用过程。

1. $fib(n) = fib(n-1) + fib(n-2)$（由树状结构隐含）

2. 基础情形$fib(0)=0, fib(1)=1$（隐含）

展示 fib(7) 的递归树结构。

1. 公式

   $$fib(7)$$
   解释

   树的根节点。

   步骤依据

   题目陈述。

   视频直接表达
2. 公式

   $$fib(6) + fib(5)$$
   解释

   第一层递归。

   步骤依据

   斐波那契数列的定义。

   视频直接表达
3. 公式

   $$fib(5) + fib(4) + fib(4) + fib(3)$$
   解释

   第二层递归，显示重复出现的 fib(4) 和 fib(5)。

   步骤依据

   斐波那契数列的定义。

   视频直接表达

一棵树状图，包含多个重复的子问题（例如，fib(5) 出现两次，fib(4) 出现三次）。

该直观图示清晰地展示了朴素递归计算斐波那契数时呈指数级增长的冗余性。

1. 图示
   观察依据

   画面展示了从旧金山到圣地亚哥的谷歌地图路线，途中标出了洛杉矶。

2. 声音
   观察依据

   讲解者说明目标是找出两座城市之间的最短路径，然后在洛杉矶处将该路径分解。

3. 公式
   观察依据

   显示方程 `SHORTEST_PATH(SF, SD) = SHORTEST_PATH(SF, LA) + SHORTEST_PATH(LA, SD)`。

1. 视频片段中未计算具体数值距离；地图上标有 `7 小时 46 分钟` 和 `530 英里`，但这些数值并未用于代数解释中。

利用地图示例，找出从旧金山到圣地亚哥的最短驾车路线。

1. 展示了一条从旧金山到圣地亚哥的路线。

2. 该路线经过洛杉矶。

3. 目标是端点之间的最短路径。

展示如何由最短的子路径构建出整体最短路线。

1. 公式

   $$\text{Identify intermediate city } LA.$$
   解释

   洛杉矶被单独指出为可将路线分割的节点。

   步骤依据

   由讲解者陈述，并在地图上高亮显示。

   视频直接表达
2. 公式

   $$\text{Solve } SF \to LA \text{ 且 } LA \to SD \text{ separately.}$$
   解释

   原问题转化为两个更小的最短路径问题。

   步骤依据

   明确描述为将问题划分为两个子问题。

   视频直接表达
3. 公式

   $$SHORTEST_PATH(SF, SD) = SHORTEST_PATH(SF, LA) + SHORTEST_PATH(LA, SD)$$
   解释

   将两个最优子结果合并，从而得到全局最优解。

   步骤依据

   展示公式并口述结论。

   视频直接表达

最短的旧金山→圣地亚哥路线，是通过将最短的旧金山→洛杉矶路线与最短的洛杉矶→圣地亚哥路线相加而获得的。

讲述者指出，该构造在本例中能保证得到整体最短路线。

1. 图示
   观察依据

   展示了计算第5个斐波那契数的递归树，其中包含重复的子树。

2. 声音
   观察依据

   讲述者称这是计算第五个斐波那契数所需的工作量，并指出存在重复调用，例如 fib(2) 和 fib(3)。

3. 字幕依据
   观察依据

   屏幕文字提及重复的函数调用和重叠子问题。

1. 该片段中未给出斐波那契数的具体数值。

利用第5个斐波那契数的递归树来说明重复计算。

1. 展示了一棵以5为根节点的递归树。

2. 一些子树会重复出现，尤其是代表2和3的那些子树。

展示重叠子问题以及朴素递归的低效性。

1. 公式

   $$\text{Compute } fib(5) \text{ recursively.}$$
   解释

   根调用代表目标斐波那契数的计算。

   步骤依据

   旁白指出该示例为第五个斐波那契数。

   视频直接表达
2. 公式

   $$\text{Observe repeated branches for } fib(3) \text{ 且 } fib(2).$$
   解释

   相同的子问题在树中多次出现。

   步骤依据

   在视觉上高亮显示，并在音频中为其命名。

   视频直接表达
3. 公式

   $$\text{Recognize this as redundant work.}$$
   解释

   重复调用完全相同的子过程意味着额外的计算，却未获得任何新信息。

   步骤依据

   讲述者将这些高亮区域称为重复工作。

   视频直接表达

斐波那契树通过重复的 fib(2) 和 fib(3) 调用，展现出重叠子问题。

冗余性通过视觉高亮显示重复子树得以验证。

1. 图示
   观察依据

   LeetCode 页面显示主题标签“动态规划474”以及文字“你已解决$34/474$道题。”

2. 声音
   观察依据

   因为如果你在 LeetCode 上浏览各类动态规划问题，实际上能从中发现共通的模式。

利用 LeetCode 动态规划问题列表来寻找反复出现的模式。

1. 一个按‘动态规划’标签筛选过的 LeetCode 页面。

2. 该页面显示该类别下共有474道题。

从实例中识别动态规划问题的实用判断指标。

1. 公式

   $$$$
   解释

   视频打开力扣（LeetCode）动态规划专题页面。

   步骤依据

   画面中可见。

   视频直接表达
2. 公式

   $$$$
   解释

   页面滚动展示大量标注为动态规划的问题，例如爬楼梯、打家劫舍、解码方法、跳跃游戏 II、不同路径、回文子串、零钱兑换、最长递增子序列、编辑距离以及单词拆分。

   步骤依据

   在滚动列表中可见。

   视频直接表达
3. 公式

   $$$$
   解释

   主讲人以此次浏览作为引子，进而提炼出五项判断指标。

   步骤依据

   音频中直接陈述。

   视频直接表达

该示例起到引出作用：浏览大量动态规划问题后，可发现反复出现的规律，这些规律可归纳为若干判断指标。

验证方式是后续幻灯片所列出的五项指标。

1. 声音
   观察依据

   “力扣上一些体现顺序决策过程的题目示例包括打家劫舍与解码方法。”

2. 图示
   观察依据

   文字显示在项目1旁：“打家劫舍（198）”和“解码方法（91）”。

列举体现顺序决策的 LeetCode 题目。

1. 该指标为顺序决策。

提供具体实例。

1. 公式

   $$$$
   解释

   主讲人以《打家劫舍》为例。

   步骤依据

   音频中直接陈述，且幻灯片上同步显示。

   视频直接表达
2. 公式

   $$$$
   解释

   主讲人以《解码方法》为例。

   步骤依据

   音频中直接陈述，且幻灯片上同步显示。

   视频直接表达

《打家劫舍》（198）与《解码方法》（91）。

两个标题及其编号均在幻灯片上可见。

1. 声音
   观察依据

   “此类问题的一些例子包括《跳跃游戏 II》和《买卖股票的最佳时机 II》。”

2. 图示
   观察依据

   文字出现在项目2旁：“《跳跃游戏 II》（45）”及“《买卖股票的最佳时机 II》（122）”。

列举体现贪心选择性质指标的 LeetCode 题目。

1. 该指标即为贪心选择性质。

提供具体实例。

1. 公式

   $$$$
   解释

   主讲人以《跳跃游戏 II》为例。

   步骤依据

   音频中直接陈述，并在幻灯片上同步显示。

   视频直接表达
2. 公式

   $$$$
   解释

   主讲人以《买卖股票的最佳时机 II》为例。

   步骤依据

   音频中直接陈述，并在幻灯片上同步显示。

   视频直接表达

《跳跃游戏 II》（45）和《买卖股票的最佳时机 II》（122）。

两个题目的标题及编号均在幻灯片上清晰可见。

1. 声音
   观察依据

   “此类问题的一些例子包括《爬楼梯》和《最小路径和》。”

2. 图示
   观察依据

   文字显示在项目3旁："CLIMBING STAIRS（70）" 和 "MINIMUM PATH SUM（64）"。

列举体现状态转移的力扣（LeetCode）题目。

1. 该指标即为状态转移。

提供具体示例。

1. 公式

   $$$$
   解释

   主讲人以《爬楼梯》为例。

   步骤依据

   在音频中直接陈述，并在幻灯片上显示。

   视频直接表达
2. 公式

   $$$$
   解释

   主讲人以《最小路径和》为例。

   步骤依据

   在音频中直接陈述，并在幻灯片上显示。

   视频直接表达

《爬楼梯》（70）与《最小路径和》（64）。

两个标题及其编号均在幻灯片上可见。

1. 图示
   观察依据

   屏幕上显示文字“唯一路径（62）”和“最长递增子序列（300）”。

2. 声音
   观察依据

   主讲人将这两个问题作为路径或数组指示器的典型示例提出。

识别符合‘路径或数组’动态规划指示器的问题。

1. 唯一路径（LeetCode 62）

2. 最长递增子序列（LeetCode 300）

提供涉及最优路径或数组排列的问题示例。

1. 解释

   主讲人列举了唯一路径和最长递增子序列作为示例。

   步骤依据

   这些问题涉及寻找最优路径或对数组中的元素进行排列。

   视频直接表达

唯一路径（62），最长递增子序列（300）。

这些示例符合路径或数组指示器的定义。

1. 图示
   观察依据

   屏幕上显示文字“零钱兑换（322）”和“最大子数组和（53）”。

2. 声音
   观察依据

   主讲人提到这些是力扣（LeetCode）上关于计数或优化指标的典型例题。

识别符合‘计数’或‘最大化/最小化’动态规划指标的问题。

1. 零钱兑换（力扣322）

2. 最大子数组和（力扣53）

提供涉及计数方案数或优化某个数值的问题示例。

1. 解释

   主讲人将零钱兑换与最大子数组和列为示例。

   步骤依据

   这些问题要求计算达成目标的方式数目，或对某个数值进行最大化或最小化。

   视频直接表达

零钱兑换（322），最大子数组和（53）。

这些示例符合计数或优化指标的定义。

1. 动画
   观察依据

   四个蓝色边框的方框从左到右依次出现，分别表示递归调用 factorial(4)、factorial(3)、factorial(2) 和 factorial(1)；随后，数字从右到左依次出现在这些方框内，分别表示返回值 1、2、6 和 24。

1. factorial(4) 的方框

2. factorial(3) 的方框

3. factorial(2) 的方框

4. 阶乘(1)的方框

5. 表示递归调用的箭头

6. 表示返回值的箭头

1. 方框从左到右依次出现。

2. 数字在方框内从右到左依次出现。

1. 方框一旦出现，其结构保持不变。

直观展示动态规划／递归中的‘分解’阶段（从左到右）和‘构建解’阶段（从右到左）。

1. 图示
   观察依据

   展示一棵大型二叉树图，节点标记为fib(7)、fib(6)、fib(5)等；部分节点以青绿色高亮，以显示重复。

1. 标记为fib(n)的节点

2. 连接父节点与子节点的边

3. 高亮的节点（例如fib(5)、fib(4)）

1. 没有，这是一张静态示意图。

1. 树状结构表示递归调用过程。

图示重叠子问题的概念：在朴素的递归方法中，同一子问题（例如 fib(5)）会被多次计算。

1. 图示
   观察依据

   一个包含两个相交圆圈的维恩图。左侧圆圈为青色，标注为“最优子结构”；右侧圆圈为黄色，标注为“重叠子问题”；两圆交集区域为绿色，标注为“动态规划问题”。

1. 青色圆圈（最优子结构）

2. 黄色圆圈（重叠子问题）

3. 绿色交集区域（动态规划问题）

1. 红色箭头指向各个圆圈，配合讲解者叙述进行指示。

1. 集合之间的空间关系。

直观地定义：动态规划问题，是同时具备最优子结构与重叠子问题这两类性质的问题的交集。

1. 图示
   观察依据

   一张标题为『动态规划问题的特征』的维恩图，包含两个重叠的圆圈，分别标注为『最优子结构』和『重叠子问题』，其交集处标注为『动态规划问题』。

1. 标题文字：“动态规划问题的特征”

2. 左侧圆圈：“最优子结构”

3. 右侧圆圈：“重叠子问题”

4. 交集处标注：“动态规划问题”

1. 图示保持静止，同时讲解员介绍第一个概念。

1. 交集持续表示这两种性质的共同存在。

该图示表明：一个动态规划问题的特征在于同时具备最优子结构与重叠子问题。

1. 图示
   观察依据

   一幅加利福尼亚州地图，显示从旧金山到圣地亚哥的一条路线，并标有指向旧金山、洛杉矶和圣地亚哥的箭头。

2. 动画
   观察依据

   文字覆盖层依次出现：“如何实现？”、“划分为2个子问题”、“保证找到整体最短路径”以及“从旧金山 → 圣地亚哥”。

3. 公式
   观察依据

   公式 `SHORTEST_PATH(SF, SD) = SHORTEST_PATH(SF, LA) + SHORTEST_PATH(LA, SD)` 出现在本段末尾附近。

1. 谷歌地图中从旧金山到圣地亚哥的路线

2. 用红色箭头标记城市。

3. 叠加文字说明子问题及保证条件。

4. 最短路径方程。

1. 路线最初以一次完整行程的形式呈现。

2. 洛杉矶被高亮显示为分割点。

3. 该问题被重新表述为两条子路线。

4. 最终方程总结了这种分解过程。

1. 在整个示例中，端点始终是旧金山和圣地亚哥。

动画将一条地理路线转化为一个展示最优子结构性质的算法分解示例。

1. 动画
   观察依据

   一个简单的白色背景动画显示 `P` 分支为 `step` 和另一个 `P`，并向下重复，直至出现 `BASE CASE`。

2. 字幕依据
   观察依据

   底部文字为 `动画演示递归如何工作`。

1. 该动画为示意性动画，除通用标签 `P` 外，并未指定任何具体函数。

1. 节点 `P`。

2. 分支标签 `step`。

3. 终止标签 `BASE CASE`。

1. 该结构逐层向下生长。

2. 每次递归调用都会生成一个新的 `step` 和一个新的 `P`。

3. 该过程在 `BASE CASE` 处终止。

1. 每一层的自引用模式都保持相同。

该动画将递归可视化为反复的自我调用，直至达到停止条件。

1. 图示
   观察依据

   以5为根的递归树展开为标记为4、3、2、1和0的节点。

2. 动画
   观察依据

   红色轮廓突出显示重复的子树，字幕中提及 `FIB(2)` 和 `FIB(3)`。

1. 屏幕上未写出确切的边规则，但该树符合标准的斐波那契递归模式。

1. 根节点5。

2. 内部节点4、3、2。

3. 叶节点1和0。

4. 红色高亮循环围绕重复的子树。

1. 首先展示完整的树。

2. 随后在视觉上强调重复区域。

3. 字幕将fib(2)和fib(3)标识为重复调用的示例。

1. 树的结构本身不发生变化；仅高亮显示和解释性覆盖层发生变化。

重复的子树使重叠子问题显现为重复的递归计算。

1. 图示
   观察依据

   展示了一棵二叉递归树，节点标有数字，并用红色圆圈标出重复的子树。

1. 该片段未明确说明此树所表示的确切递推关系。

1. 根节点标记为5

2. 内部节点标记为4、3、2

3. 叶节点标记为1和0

4. 用红色圆圈标出重复的子树

1. 解说内容从识别重叠子问题出发，逐步说明递归与动态规划之间的关系。

2. 红色圆圈位置固定不变，而树下方的字幕随之变化。

1. 在此时间段内，树的结构本身不发生动画效果。

2. 重复的子树始终保持红色高亮状态。

静态树直观地表明：递归分解可能多次重新访问同一子问题，从而支持重叠子问题这一概念。

1. 图示
   观察依据

   出现一个标题为“动态规划问题的特征”的韦恩图。

1. 左侧圆圈标注为“最优子结构”

2. 右侧圆圈标注为“重叠子问题”

3. 交集处标注为“动态规划问题”

1. 画面从递归树切换至韦恩图。

2. 在图表区间内不再发生任何动画。

1. 双集合结构保持固定。

2. 交集处的标注始终可见。

该图表总结了这一概念性论断：动态规划问题由最优子结构与重叠子问题二者的交集所刻画。

1. 图示
   观察依据

   垂直滚动一个按‘动态规划’筛选的力扣（LeetCode）页面。

1. 专题标签“动态规划474”

2. 题目行，含标题、通过率及难度标识

3. 侧边栏显示各公司题目数量

1. 页面向下滚动，展示大量动态规划问题。

2. 光标先移至主题区域，再开始滚动。

1. 页面始终保留在力扣（LeetCode）界面内。

2. 列表始终保持动态规划分类的筛选状态。

该滚动示例旨在引导观众从关注形式化特征，转向在大量动态规划问题中识别实际模式。

1. 图示
   观察依据

   一张标题为“5 动态规划识别标志”的幻灯片列出五项带编号的内容，随着讲解推进，当前项以红色高亮显示。

1. 第4项仅在本片段结尾处首次出现，且在所提供时长内未作解释。

1. 标题：“5 动态规划识别标志”

2. 编号列表项1至5

3. 出现在编号项1至3旁的例题标签

1. 随着讲解推进，高亮依次从第1项移至第2项，再移至第3项。

2. 示例问题名称显示在对应指标的旁边。

1. 全部五个指标的列表始终保留在屏幕上。

2. 幻灯片格式保持不变。

该幻灯片整理了动态规划问题的实际识别启发式方法，并将每个指标与命名的 LeetCode 示例关联起来。

1. 图示
   观察依据

   第四项‘4. 路径或数组’以红色高亮显示，其余项为白色。

1. 5个动态规划指标列表

1. 第4项变为红色

1. 第1、2、3和5项保持白色

引导观众注意力至当前正在讨论的主题。

1. 声音
   观察依据

   讲解者进一步说明：“该术语中的‘编程’并非指编码意义上的编程；贝尔曼当时使用‘programming’一词，意指规划与决策过程。”

学习者常常误以为‘动态规划’中的‘编程’指的是编写计算机代码。

在此语境中，‘编程’实指规划与决策制定，这一用法由理查德·贝尔曼首创。

1. 声音
   观察依据

   讲解员说：‘现在，递归是一个值得单独制作视频的主题，但在此例中我们仅简要提及。’

观众可能会认为这段视频完整地解释了递归。

该视频明确限定自身仅作一个简短的、以示例为导向的递归入门介绍，目的是为了说明重叠子问题。

1. 声音
   观察依据

   在指出重叠子问题是问题彼此重叠之后，讲解者问道：‘这显然没错，但这句话究竟意味着什么？’

2. 图示
   观察依据

   随后，视频借助斐波那契树来具体定义这一术语。

若按字面意思理解，‘问题重叠’这一说法听起来是同义反复。

该片段通过展示计算树中重复出现的递归调用（例如 fib(2) 和 fib(3)）来澄清这一术语。

1. 声音
   观察依据

   “如果你能用贪心算法解决一个问题，那么你也能用动态规划来解决它。”

1. 该片段将此表述为一种启发式关系，并未讨论反例或局限性。

人们可能认为，如果一个问题能用贪心法求解，那它就不是动态规划问题。

视频明确指出相反观点：如果一个问题能用贪心算法求解，那么它也能用动态规划求解。

1. 声音
   观察依据

   主讲人建议首先检查该问题是否可递归求解，再据此推断其是否适用于动态规划。

1. 该片段未单独解释记忆化与制表法的区别。

有人在将问题分解后，可能会止步于朴素递归。

视频将递归用作诊断步骤，然后指出：一旦存在重叠子问题和最优子结构的逐层构建特性，动态规划便是更高效的求解方法。

1. 图示
   观察依据

   文氏图将‘最优子结构’列为‘动态规划问题’的必要组成部分。

动态规划的定义本身即以内含‘最优子结构’这一性质为前提。

1. 图示
   观察依据

   文氏图将‘重叠子问题’列为‘动态规划问题’的必要组成部分。

动态规划的定义本身即以内含‘重叠子问题’这一性质为前提。

1. 图示
   观察依据

   文氏图将‘动态规划问题’置于‘最优子结构’与‘重叠子问题’两个集合的交集之中。

通用的动态规划特征描述包含最优子结构，作为其两项必要性质之一。

1. 声音
   观察依据

   讲解者将重叠子问题作为第二项特征加以引入。

2. 图示
   观察依据

   文氏图以及后续的斐波那契树，均将这一性质与动态规划联系起来。

动态规划的特征描述同样将重叠子问题列为第二项必要性质。

1. 声音
   观察依据

   在介绍最优子结构后，立即使用最短路径示例进行说明。

2. 公式
   观察依据

   该方程直接表达了最优子结果的组合。

路线示例将最优子结构的定义应用于一个具体的最短路径问题。

1. 动画
   观察依据

   通用递归动画出现在斐波那契树之前。

2. 声音
   观察依据

   讲解者借助递归说明重复调用的来源。

对递归自调用的理解被用作识别斐波那契树中重复子问题的背景知识。

1. 声音
   观察依据

   斐波那契递归树被明确呈现为重叠子问题的最简单示例。

斐波那契示例将重叠子问题这一抽象概念应用于一个可见的递归计算过程。

1. 声音
   观察依据

   讲解者指出，动态规划有助于消除重复计算。

动态规划框架被呈现为专门解决由重叠子问题所导致的低效问题的方法。

1. 声音
   观察依据

   旁白将重叠子问题与“动态规划能更高效地解决该问题”这一论断联系起来。

2. 图示
   观察依据

   递归树凸显了重复出现的子树。

识别重叠子问题被呈现为判断动态规划是否适用所需满足的条件之一。

1. 声音
   观察依据

   主讲人先提到“这两个条件”，随后又说“这正是两个主要特征”。

2. 图示
   观察依据

   维恩图明确标出了这两个特征的名称。

口头表述的双条件检验与维恩图所表达的是同一套关于动态规划问题的概念性判据。

1. 声音
   观察依据

   在总结完两个主要特征后，主讲人说道：“但在本视频结束之前，我想谈谈几个你可以留意的模式。”

2. 图示
   观察依据

   画面从维恩图切换至“5动态规划指示器”幻灯片。

这五个指示器是在阐明形式化特征之后，通过对大量动态规划问题的观察而提炼出的实用模式。

1. 图示
   观察依据

   项目 1 在“5 动态规划指标”幻灯片上是“序贯决策”。

2. 声音
   观察依据

   其中第一个是序贯决策。

序贯决策是五指标列表中的一项。

1. 声音
   观察依据

   讲解者给出动态规划的定义。

1. 动态规划的定义

1. 公式
   观察依据

   以阶乘为例来解释递归以及逐步构建解的过程。

1. 动态规划的定义
2. 阶乘的递归分解
3. 递归计算4!

1. 声音
   观察依据

   讲解者列出动态规划问题所需的两个条件。

2. 图示
   观察依据

   维恩图展示了这两个条件。

1. 动态规划的适用条件
2. 最优子结构
3. 重叠子问题

1. 声音
   观察依据

   讲述者解释了此处“编程”一词的历史含义。

1. 对动态规划中‘编程’一词的常见误解

1. 声音
   观察依据

   讲解者用语言定义了最优子结构，并以路线示例加以图示说明。

1. 最优子结构
2. 从旧金山到圣地亚哥的最短路径
3. 从地图示例出发推导最短路径方程。

1. 图示
   观察依据

   在地图示例中，洛杉矶被标为中间点。

2. 公式
   观察依据

   最短路径方程以洛杉矶为分割点进行构建。

1. 从旧金山到圣地亚哥的最短路径
2. 从地图示例出发推导最短路径方程。
3. 最短路径分解主张

1. 声音
   观察依据

   讲述者先引入重叠子问题的概念，再通过重复调用加以解释。

2. 图示
   观察依据

   斐波那契树展示了重复出现的子树。

1. 重叠子问题
2. 以斐波那契递归树作为重叠子问题的示例。
3. 在斐波那契递归树中展示重叠子问题

1. 图示
   观察依据

   递归树中高亮显示了重复出现的 fib(2) 和 fib(3) 子树。

1. 以斐波那契递归树作为重叠子问题的示例。
2. 在斐波那契递归树中展示重叠子问题
3. 重叠子问题

1. 动画
   观察依据

   一个简单的 P → 步骤 → P 动画最终停在基础情形。

1. 递归即函数自我调用，直至抵达基准情形
2. 通用递归动画

1. 声音
   观察依据

   “如果满足这两个条件……”

2. 图示
   观察依据

   维恩图标注了这两个条件。

1. 应用动态规划的两个条件
2. 动态规划问题的特征

1. 声音
   观察依据

   主讲人将尝试递归和分治法作为一种检验手段。

1. 检验一个问题是否适合动态规划的方法
2. 应用动态规划的两个条件

1. 声音
   观察依据

   “那么它将表现出重叠子问题。”

2. 图示
   观察依据

   重复出现的子树用红色圆圈标出。

1. 重叠子问题