动态规划基础：从暴力到优雅的蜕变

动态规划，简称 DP。说实话，我刚入行时觉得这玩意儿特别玄乎。什么「状态转移方程」、「最优子结构」，听着就像数学竞赛题。直到我在一个嵌入式项目中，遇到了实时路径规划的问题——暴力递归跑一次要 3 秒，用户按一下遥控器要等 3 秒才有反应，这谁受得了？

后来我用 DP 重构，把时间降到了 10 毫秒以内。嗯，从那天起，我就彻底服了。

一、动态规划的基本思想

动态规划的核心思想，说白了就八个字：记住过去，避免重复。

你想想看，我们平时写递归，经常遇到同一个子问题被反复计算的情况。比如斐波那契数列，递归写法里 fib(5) 要算 fib(4) 和 fib(3)，而 fib(4) 又要算 fib(3) 和 fib(2)…… fib(3) 被算了两次。n 一大，指数级爆炸。

动态规划的做法是：把已经算过的结果存起来，下次要用直接取。这就是所谓的「记忆化搜索」或者「填表法」。

我个人习惯，拿到一个问题先问自己三个问题：

1. 这个问题能不能拆成更小的子问题？
2. 子问题之间有没有重叠？
3. 子问题的最优解能不能推导出原问题的最优解？

如果三个答案都是「是」，那 DP 基本就稳了。

二、最优子结构

最优子结构，听起来很学术。其实意思很简单：一个问题的最优解，包含了它的子问题的最优解。

举个例子。你要从北京开车到上海，想找一条最短路径。如果你经过济南，那么北京到济南这一段，也必须是北京到济南的最短路径。否则，你完全可以换一条更短的北京→济南路线，整体路径就更短了——这就矛盾了。

我在项目中遇到过一个问题：嵌入式设备上的任务调度，要最小化总能耗。每个任务可以选择不同的电压/频率组合。我发现，如果前 k 个任务的最优调度方案里，第 k 个任务选了某个频率，那么前 k-1 个任务的调度方案，也必须是它们自己的最优方案。这就是典型的最优子结构。

三、重叠子问题

重叠子问题，就是同一个子问题被反复计算。这是 DP 能优化的根本原因。

你看下面这个递归树，计算 fib(5)：

fib(5)
├── fib(4)
│   ├── fib(3)
│   │   ├── fib(2)
│   │   └── fib(1)
│   └── fib(2)
└── fib(3)
    ├── fib(2)
    └── fib(1)

fib(3) 被算了两次，fib(2) 被算了三次。n=40 的时候，递归调用次数是恐怖的 3.3 亿次。而用 DP 只需要算 40 次。

怎么判断有没有重叠子问题？我有个土办法：画递归树，看同一个节点出现几次。出现两次以上，就有重叠。

四、0-1 背包问题

0-1 背包是 DP 的经典入门题。场景是这样的：

你有一个背包，容量为 W。有 n 个物品，每个物品有重量 w[i] 和价值 v[i]。每个物品要么拿（1），要么不拿（0），不能拿一半。问：能装进背包的最大总价值是多少？

我第一次做这道题时，想的是贪心——按价值/重量比排序，先装性价比高的。结果发现不对。为什么？因为背包容量是离散的，性价比高的可能塞不进去，反而两个性价比低的组合起来更优。

好，我们来看 DP 解法。

状态定义

dp[i][j] 表示：前 i 个物品中，选出总重量不超过 j 的物品，能获得的最大价值。

状态转移方程

对于第 i 个物品，有两种选择：

• 不拿：dp[i][j] = dp[i-1][j]（继承前 i-1 个物品的结果）
• 拿：dp[i][j] = dp[i-1][j - w[i]] + v[i]（前提是 j >= w[i]）

取两者最大值：

dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + v[i])

代码实现

#include <stdio.h>
#define max(a, b) ((a) > (b) ? (a) : (b))

int knapsack(int W, int w[], int v[], int n) {
    int dp[n+1][W+1];
    
    // 初始化：0 个物品时价值为 0
    for (int j = 0; j <= W; j++) dp[0][j] = 0;
    
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= W; j++) {
            if (j < w[i-1]) {
                // 装不下，只能不拿
                dp[i][j] = dp[i-1][j];
            } else {
                // 装得下，比较拿和不拿哪个更优
                dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i-1]] + v[i-1]);
            }
        }
    }
    return dp[n][W];
}

int main() {
    int w[] = {2, 3, 4, 5};
    int v[] = {3, 4, 5, 6};
    int W = 8;
    int n = sizeof(w) / sizeof(w[0]);
    printf("最大价值: %d\n", knapsack(W, w, v, n));
    return 0;
}

空间优化

你发现没有？dp[i][j] 只依赖 dp[i-1][...] 这一行。所以我们可以把二维数组压缩成一维：

int dp[W+1] = {0};
for (int i = 0; i < n; i++) {
    // 注意：必须倒序遍历，否则会重复使用同一个物品
    for (int j = W; j >= w[i]; j--) {
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    }
}

为什么倒序？因为正序遍历时，dp[j - w[i]] 可能已经被本轮更新过了，相当于同一个物品拿了多次——那就变成「完全背包」问题了。我曾经在面试时犯过这个错，被面试官一眼看穿，尴尬得不行。

五、知识体系总览

下面这张图，是我自己总结的 DP 学习路线。每次带新人我都先给他们看这个：

六、总结

动态规划不是什么高深莫测的东西。它就是一个「用空间换时间」的策略。你记住子问题的答案，避免重复计算，就能把指数级复杂度降到多项式级别。

我个人觉得，学 DP 最好的方式就是多做题、多画表。拿张纸，把 dp 表格一行一行填出来，比看十遍理论都管用。我在带团队时，遇到 DP 问题从来不让新人直接写代码——先给我把表格画清楚，画清楚了再动手。

最后送你一句话：DP 难的不是代码，是状态定义。定义对了，方程自然就出来了。

---

公众号:蓝海资料掘金营，微信deep3321