动态规划

动态规划是把大问题拆解成重复出现的子问题，保存子问题的计算结果避免重复运算，通过子问题最优解逐步推导出原问题最优解的算法思想，常用于计数、求最值类问题。

January 1, 1990算法设计2分钟阅读

直接优化与动态规划对比。直接优化沿着路径向前搜索；动态规划从目标终端状态逆向回推各个状态最优解。

抽象来说，动态规划（Dynamic Programming，简称 DP）是这样一种算法思想：将一个复杂的整体问题巧妙地分解为一系列子问题，在解决每个子问题时利用“状态数组”进行记忆化存储，从而通过小问题的解逐步递推出大问题的解。在这个过程中，如何将无数种可能的计算状态抽象并整合成有限的 “子问题”，即 “汇总搜索情况”，正是破解 DP 的核心关键。

我们通过解决一个简单的问题，引出动态规划中的各种概念。

【问题场景】

有 $N$ 个石头，编号为 $1$ 到 $N$ 。每个石头 $i$ 都有一个高度 $h_i$ 。一只青蛙最初在石头 $1$ 上。当青蛙在石头 $i$ 上时，它可以跳到石头 $i+1$ 或石头 $i+2$ 上。这一跳的 代价（Cost） 是 $\vert{}h_i - h_j\vert{}$ （两石头高度差的绝对值）。求青蛙到达石头 $N$ 所需的最小总代价。

当我们盯着终点石头 $N$ 时，不妨倒过来想：青蛙到达石头 $N$ 的最后一步，是从哪里来的？

由于青蛙一次只能跳 1 步或 2 步，它只可能从两个地方跳到 $N$ ：要么从石头 $N-1$ 跳过来，要么从石头 $N-2$ 跳过来。

如果我们已经知道了“到达石头 $N-1$ 的最小代价”以及“到达石头 $N-2$ 的最小代价”，那么到达石头 $N$ 的最小代价，就纯粹取决于这两种抉择中哪一个的总和更小。大问题的最优解，完全可以由小问题的最优解组合而成。在动态规划中，这个特性被称为最优子结构 (Optimal Substructure)。

如果我们用盲目的暴利穷举去算这道题，会发现从石头 4 跳到石头 6，或者从石头 5 跳到石头 6 后，后续面临的“从石头 6 出发到终点”的子问题是完全一样的，却会被重复计算无数次。这种现象称为重叠子问题 (Overlapping Subproblems)。

为了消除重复计算，动态规划的策略是“定义状态”——设计一个“账本”把子问题的解记录下来。

我们定义一个一维数组 dp：

dp[i] 表示：青蛙从石头 1 跳到石头 $i$ 的最小总代价。

通过这个账本，每个子问题只用计算一次，我们的最终目标就是求出 dp[N]。所谓动态规划，本质上就是这种通过将原问题分解为相对简单的子问题，并通过组合记录子问题的解来求解复杂问题的方法。

有了账本，我们需要知道数据之间如何流动。基于前面发现的“最后一步”逻辑，我们能够建立起子问题之间的逻辑纽带。青蛙要到达石头 $i$ ，只有两种可能：

从石头 $i-1$ 跳过来，总代价为： $dp[i-1] + \vert{}h_i - h_{i-1}\vert{}$
从石头 $i-2$ 跳过来，总代价为： $dp[i-2] + \vert{}h_i - h_{i-2}\vert{}$

因为我们要找的是最小代价，所以取两者的极小值。这就是动态规划的核心——状态转移方程 (Transition Equation)：

$dp[i] = \min(dp[i-1] + \vert{}h_i - h_{i-1}\vert{}, dp[i-2] + \vert{}h_i - h_{i-2}\vert{})$

最后，没有初始值，这个递推引擎就无法启动。我们需要初始化边界条件 (Base Cases)：

dp[1] = 0 （青蛙本来就在石头 1，不需要付出任何代价）
dp[2] = |h_2 - h_1| （石头 2 只能从石头 1 一步跳过来）

至此，通过“定义状态 $\rightarrow$ 状态转移 $\rightarrow$ 边界初始化”的完整步骤，青蛙问题便迎刃而解，我们也顺理成章地掌握了动态规划的核心运作机制。

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

int main() {
    // 优化输入输出流，加速执行
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    if (!(cin >> N)) return 0;

    vector<int> h(N + 1);
    for (int i = 1; i <= N; ++i) {
        cin >> h[i];
    }

    // dp[i] 表示到达石头 i 的最小总代价
    vector<int> dp(N + 1, 0);

    // 1. 初始化边界条件
    dp[1] = 0;
    if (N >= 2) {
        dp[2] = abs(h[2] - h[1]);
    }

    // 2. 状态转移
    for (int i = 3; i <= N; ++i) {
        dp[i] = min(dp[i - 1] + abs(h[i] - h[i - 1]),
                    dp[i - 2] + abs(h[i] - h[i - 2]));
    }

    // 3. 输出最终目标
    cout << dp[N] << "\n";

    return 0;
}

在“青蛙跳石”问题中，动态规划将复杂的全局路径搜索转化为高效的 “流水线作业”。它将看似庞大的长远规划拆解为局部抉择——青蛙每走到一块石头，只需二选一判断从前一步还是前两步跳过来更省力。

为了实现这种转化，它利用“账本”消灭了无休止的重复计算，让每块石头的最小代价只算一次，直接将计算时间从指数级降到了线性级 $O(N)$ 。最后，算法以起点为地基，像砌砖一样顺着石头编号正向递推填表，每一步都踩在过去算好的最优解之上，最终在终点顺理成章地摘取全局最优答案。

我们以 3 个石头为例，假设它们的高度分别为 $h = [10, 30, 40]$ （为方便对应，令下标从 1 开始，即 $h[1]=10, h[2]=30, h[3]=40$ ）。接下来，我们结合这个具体场景来介绍动态规划中的相关概念。

“松弛”这个词源于图论（如 Dijkstra 最短路径算法）。在动态规划中，它指的是尝试用一条新找到的路径（或解），去更新并优化当前状态的操作。

假设青蛙想去石头 3（高度 40）。一打开账本，我们发现 dp[3] 记录的初始代价是无穷大（ $\infty$ ）。

第一次松弛： 青蛙尝试从石头 1（高度 10，dp[1]=0）一脚大跳过来。

计算代价： $0 + \vert{}40 - 10\vert{} = 30$ 。因为 $30 < \infty$ ，我们将 dp[3] 更新为 30。这完成了一次松弛。

第二次松弛： 随后，青蛙发现也可以从石头 2（高度 30，假设已知 dp[2]=20）跳一步过来。

计算代价： $20 + \vert{}40 - 30\vert{} = 30$ 。因为 $30$ 没有比当前的记录更小，所以这次松弛没有改变 dp[3] 的值。

在代码中，松弛通常表现为这样的形式：

dp[to] = min(dp[to], dp[from] + cost);

视角： 站在当前未知状态的立场，向过去“拉取”已知数据。
核心逻辑： “我是石头 3，我准备计算我的 dp[3]。我看一眼前面已经算好的 dp[2] 和 dp[1]，把它们的值拉过来，加上跳跃代价，算出一个最小值填进我自己的格子。”

计算循环轮到 i = 3 时，青蛙站在石头 3 上向后看：

从石头 2 拉取数据：dp[2] (20) + $\vert{}40 - 30\vert{}$ = 30

从石头 1 拉取数据：dp[1] (0) + $\vert{}40 - 10\vert{}$ = 30

比较后，把最终答案 30 填入 dp[3]。

// 数组下标从 1 开始
for (int i = 3; i <= N; i++) {
    dp[i] = min(dp[i-1] + abs(h[i] - h[i-1]),
                dp[i-2] + abs(h[i] - h[i-2]));
}

视角： 站在当前已知状态的立场，向未来“推送”自己的贡献。
核心逻辑： “我是石头 1，我的 dp[1] = 0 已经是最优解了。我要看看我能跳到哪里去。我可以跳到石头 2 和石头 3，那我就用我当前的数据去尝试更新（松弛） dp[2] 和 dp[3] 的值。”

计算循环轮到 i = 1 时，此时 dp[1] = 0 已知，后续所有 dp 均为 $\infty$ 。

向未来石头 2 推送：用 dp[1] (0) + $\vert{}30 - 10\vert{}$ 去尝试松弛 dp[2]，成功将 dp[2] 从 $\infty$ 刷新为 20。

向未来石头 3 推送：用 dp[1] (0) + $\vert{}40 - 10\vert{}$ 去尝试松弛 dp[3]，成功将 dp[3] 从 $\infty$ 刷新为 30。

// 初始化 dp 数组为无穷大 (INF)，dp[1] = 0
for (int i = 1; i < N; i++) {
    // 向未来石头 i+1 推送
    dp[i+1] = min(dp[i+1], dp[i] + abs(h[i+1] - h[i]));
    // 向未来石头 i+2 推送（注意防越界）
    if (i + 2 <= N) {
        dp[i+2] = min(dp[i+2], dp[i] + abs(h[i+2] - h[i]));
    }
}

在算法的世界里，动态规划（Dynamic Programming）本质上并不是什么凭空出现的魔法，它只是“聪明地进行穷举搜索”——也就是带记忆的穷举（Memoization）。

我们可以通过青蛙跳石的例子，看看动态规划是如何从最原始的暴利穷举，一步步进化而来的。

面对“求到达终点 $N$ 的最小代价”，最直观的想法就是把所有可能的跳法都试一遍。

青蛙在终点 $N$ ，倒过来想，它只有两种合法的来源：要么从 $N-1$ 跳过来，要么从 $N-2$ 跳过来。于是我们可以写一个递归函数 solve(i) 来穷举所有路径：

要想知道到达 $i$ 的最小代价，就去问到达 $i-1$ 和 $i-2$ 的最小代价是多少。
然后在这两种来源中选一个代价更小的。

// 纯穷举搜索（暴利递归）
int solve(int i, const vector<int>& h) {
    if (i == 1) return 0;
    if (i == 2) return abs(h[2] - h[1]);

    // 盲目穷举两种可能，并向下展开深不见底的递归树
    return min(solve(i - 1, h) + abs(h[i] - h[i - 1]),
               solve(i - 2, h) + abs(h[i] - h[i - 2]));
}

代价：这棵穷举树会呈指数级（ $O(2^N)$ ）疯狂膨胀。当 $N=40$ 时，计算机就会因为重复计算同一块石头而陷入卡死状态。

我们在穷举时发现了一个极其愚蠢的现象：为了算 solve(6)，我们需要算 solve(5) 和 solve(4)；而算 solve(5) 时，又会去算一遍 solve(4)。

这块编号为 4 的石头，在源源不断的递归分支中被重复计算了无数次。然而，无论青蛙是从哪里跳到石头 4 的，“从石头 1 到石头 4 的最小代价”这件事情是永远不会变的。

于是，我们拿出一个“备忘录”（数组或哈希表），一旦算出了某块石头的答案，就立刻记下来。下次穷举再遇到它时，直接翻账本查答案，绝不再算第二遍：

// 带记忆的穷举搜索（记忆化递归 / 自顶向下动态规划）
vector<int> memo(N + 1, -1); // 初始化备忘录为 -1，表示没算过

int solve(int i, const vector<int>& h) {
    if (i == 1) return 0;
    if (i == 2) return abs(h[2] - h[1]);

    // 核心：如果备忘录里有记录，直接返回，斩断重复的穷举分支
    if (memo[i] != -1) return memo[i];

    // 只有没算过，才进行穷举
    memo[i] = min(solve(i - 1, h) + abs(h[i] - h[i - 1]),
                  solve(i - 2, h) + abs(h[i] - h[i - 2]));
    return memo[i];
}

通过这层“记忆化”外壳，原本庞大的指数级递归树被拦腰斩断，每块石头仅仅被真正计算了一次。时间复杂度瞬间从 $O(2^N)$ 降到了 $O(N)$ 。

这，就是动态规划的雏形。

既然我们已经知道，记忆化穷举的本质就是“计算并查表”，而且大石头的答案一定依赖于小石头的答案，那我们为什么还要写复杂的递归呢？

我们干脆连递归的衣服都脱掉，直接从最简单的起点（石头 1 和 2）开始，顺着 for 循环正向填表。这便是我们最终看到的、最纯粹的动态规划代码：

// 摒弃递归，直接正向查表递推
dp[1] = 0;
dp[2] = abs(h[2] - h[1]);

for (int i = 3; i <= N; ++i) {
    // 这里的 dp[i-1] 和 dp[i-2] 就是我们之前穷举并记录下来的“熟人”
    dp[i] = min(dp[i - 1] + abs(h[i] - h[i - 1]),
                dp[i - 2] + abs(h[i] - h[i - 2]));
}

将 带记忆化的穷举搜索 与 动态规划（基于拉取形式） 中的松弛处理进行比较：

等价替换：通过将当前状态的计算结果 solve(i) 替换为 dp[i]，并将 solve(i - 1) 和 solve(i - 2) 分别替换为 dp[i - 1] 和 dp[i - 2]，可以看出这两者执行的是完全相同的松弛处理。
核心结论：由此可知，记忆化递归实际上可以被视为通过递归函数实现的动态规划。

在这里，我们回顾一下记忆化递归中 dp 数组的含义。数组 dp 用于对通过递归函数进行穷举搜索获得的结果进行记忆化。换句话说，变量 dp[i] 中包含从石头 1 到石头 $i$ 的搜索结果的精简总结。通过这种方式，算法实现了将可被总结的搜索情况汇总在一起、并避免重复计算的设计，从而实现了显著的加速。这种 “汇总搜索情况” 的思想，正是动态规划的核心。