核心思想 #

• 逻辑复用：从终点反推，存储子问题的解，避免重复计算。
• 反向传播：本质是在计算图上执行 DP。从误差（Loss）开始，利用链式法则反向传递梯度，高效更新参数。
• 效率对比：
  • 从前往后：面临指数级分支，需遍历所有路径。
  • 从后往前：每一阶段只保留最优状态，极大压缩搜索空间。

动态规划的两大前提 #

实战案例 A：最短路径（最优子结构） #

场景：从 A 出发，经过 B 或 C，最终到达 D。

• 数据：$A \to B(3)$，$A \to C(10)$；$B \to D(8)$，$C \to D(2)$。
• 状态定义：$dp[i]$ 为节点 $i$ 到终点 $D$ 的最短距离。

graph LR
    A((A)) -- 3 --- B((B))
    A((A)) -- 10 --- C((C))
    B((B)) -- 8 --- D((D))
    C((C)) -- 2 --- D((D))
    style D fill:#f96,stroke:#333

倒序推导逻辑：

1. 边界：已知 $dp[B] = 8$，$dp[C] = 2$。

2. 决策起点 A：

   • 方案 1：经过 B $\to$ $Dist(A,B) + dp[B] = 3 + 8 = 11$。
   • 方案 2：经过 C $\to$ $Dist(A,C) + dp[C] = 10 + 2 = 12$。

3. 转移方程：$dp[A] = \min(11, 12) = 11$。

结论：虽然第一步去 B 看起来更近，但 DP 通过提前计算 $dp[B]$ 和 $dp[C]$，使得起点 A 在决策时能看到“全局代价”。

实战案例 B：连续走直线得分翻倍（解决后效性） #

原始问题：走到 $(x, y)$ 时，若之前连续走了 2 次直线，则下一步走直线得分翻倍。

痛点：普通状态 $dp[x][y]$ 无法处理。因为“现在怎么走”取决于“过去怎么来的”（有后效性）。

解决方法：升维（增加状态空间）

• 将状态改为 $dp[x][y][k]$，其中 $k$ 代表到达当前格子时已经连续走直线的次数（$k=0, 1, 2$）。

状态转移逻辑：

• 如果下一步转弯：转移到 $dp[next_x][next_y][0]$（计数清零）。
• 如果下一步走直线：从 $dp[x][y][1]$ 转移到 $dp[next_x][next_y][2]$（计数加一，并触发得分翻倍奖励）。

结论：通过把“过去的影响”强行变成“当前状态的一部分”，重新让问题符合无后效性。

实战案例 C：带权重的区间调度 #

假设有一系列讲座 $i$，每个讲座有：

• 开始时间 $s_i$
• 结束时间 $f_i$
• 价值/权重 $v_i$（在简单版本中，$v_i$ 恒等于 1）

目标是选择一组互不冲突的讲座，使得总价值 $\sum v$ 最大。

动态规划: 全局权衡 #

为了解决价值不等的情况，我们必须按结束时间排序，并定义状态 $DP[i]$ 为前 $i$ 个讲座的最优解。

• 状态转移方程：

$$DP[i] = \max(DP[i-1], v_i + DP[pre_i])$$

• 逻辑分支：
  • 选项 1 ($DP[i-1]$)：放弃当前讲座，保留之前的最优结果。
  • 选项 2 ($v_i + DP[pre_i]$)：接受当前讲座价值，并加上上一个兼容位置的最优结果。
• 核心：DP 必须不断比较这两个选项，因为当前讲座虽然有价值，但它可能排斥掉后面价值更高的讲座。

贪心算法：权重相同时的特例 #

当所有讲座的权重 $v$ 恒等于 1 时，上述 DP 方程发生了显著的简化。

• 价值恒定导致性质变化：由于每个讲座的价值都一样，我们不再需要为了“高价值”而等待。
• 时间窗的决定性：在价值相同的前提下，唯一能影响全局收益的变量就是“剩余时间”。
• 决策路径塌缩：如果选一个结束时间更晚的讲座，它能带来的价值依然是 1，但它压缩了后续的选择空间。
• 结论：在 $v=1$ 时，选择“结束时间最早”的讲座永远不会比其他选择更差。

动态规划与贪心算法的关系 #

在算法设计中，区间调度（听讲座数量最多）通常被视为贪心算法的入门案例。然而，通过引入“权重”概念并写出其动态规划方程，我们可以发现：贪心算法并非独立于 DP 之外的技巧，而是 DP 在特定约束下（权重恒定）的一种路径塌缩。

为什么说贪心是 DP 的“塌缩”？ #

• 搜索空间的修剪：在 DP 过程中，我们需要维护一个表来记录所有子问题的解。但在权重相同时，我们发现最优解永远出现在“能放得下的、结束最早的”那条路径上。
• 逻辑直觉：
  • DP 像是一个精明的商人，计算每一笔交易的盈亏。
  • 贪心像是一个高效的收纳员，因为所有东西价值一样，他只需要考虑如何塞进更多的东西。
• 数学本质：当满足“贪心选择性质”时，DP 的状态转移方程中，$\max$ 函数的其中一个分支变得恒优于另一个分支，从而失去了比较的必要。

实现方式：递归 vs 循环 #

递归（自顶向下）：

• 逻辑直观，符合人类思维。
• 通过缓存避免重复计算。

循环（自底向上）：

• 正向加速：从小问题到大问题顺序填表。
• 性能更高，无递归栈溢出风险。