动态规划（上）：从思想到实战

动态规划，简称 DP。很多初学者一听这名字就头大。说实话，我当年刚接触时也懵——这玩意儿到底在干嘛？

后来做项目多了，慢慢就悟了。动态规划说白了就一句话：把大问题拆成小问题，记住小问题的答案，避免重复计算。

嗯，就这么简单。但真正用好它，需要一点技巧。

动态规划的核心思想

先问大家一个问题：你手头有 100 个任务，每个任务耗时不同。你想知道完成所有任务的最短时间，你会怎么做？

最笨的办法：把所有排列组合都试一遍。100 个任务，排列数是 100!，宇宙毁灭都算不完。

动态规划的思路不一样。它会说：先解决第 1 个任务，再解决剩下的 99 个。而解决剩下的 99 个，又可以用同样的思路——先解决第 2 个，再解决剩下的 98 个。以此类推。

这就是「最优子结构」：大问题的最优解，包含了子问题的最优解。

还有一个关键点：子问题会重复出现。比如你计算第 5 个任务时，可能要用到第 3 个任务的结果。如果你每次都重新算，那就白费功夫了。所以我们要「记忆化」——把算过的结果存起来，下次直接用。

我个人习惯把 DP 问题分成两类：「自顶向下」（递归+记忆化）和 「自底向上」（迭代填表）。前者好理解，后者效率高。咱们先看一个经典例子。

斐波那契数列：DP 入门第一课

斐波那契数列的定义很简单：F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)。

很多教材一上来就写递归：

int fib(int n) {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2);
}

这段代码看着简洁，但性能极差。为什么？因为它在疯狂重复计算。你算一下 fib(5)，它要算 fib(4) 和 fib(3)；算 fib(4) 又要算 fib(3) 和 fib(2)……fib(3) 被算了两次，fib(2) 被算了三次。n 越大，重复越多，时间复杂度是 O(2^n)。

我在项目中遇到过类似的问题——一个递归算法跑了几分钟没出结果。后来一查，就是这种重复计算在作怪。

用 DP 改一下：

// 自底向上，迭代填表
int fib_dp(int n) {
    if (n <= 1) return n;
    int dp[n+1];
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}

时间复杂度降到了 O(n)，空间复杂度也是 O(n)。

还能再优化吗？当然可以。你想想看，我们真的需要存整个数组吗？其实只需要记住前两个值就够了：

int fib_opt(int n) {
    if (n <= 1) return n;
    int a = 0, b = 1, c;
    for (int i = 2; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return c;
}

空间复杂度降到了 O(1)。这就是 DP 的威力——不仅算得快，还能省内存。

0-1 背包问题：经典中的经典

背包问题是我面试时最爱问的题目之一。因为它能很好地考察一个人的抽象能力。

问题描述：有一个背包，容量为 W。有 n 个物品，每个物品有重量 w[i] 和价值 v[i]。每个物品只能选一次（这就是「0-1」的含义——要么拿，要么不拿）。问能装的最大价值是多少？

我第一次做这题时，想的是贪心——先拿单位重量价值最高的。结果发现不对。为什么？因为背包有容量限制，贪心可能装不满，反而浪费了空间。

后来用 DP 才真正解决。

定义状态：dp[i][j] 表示「前 i 个物品中，选出总重量不超过 j 的最大价值」。

转移方程：

• 不拿第 i 个物品：dp[i][j] = dp[i-1][j]
• 拿第 i 个物品：dp[i][j] = dp[i-1][j - w[i]] + v[i]（前提是 j >= w[i]）
• 取两者最大值

代码实现：

int knapsack(int W, int n, int w[], int v[]) {
    int dp[n+1][W+1];
    // 初始化
    for (int i = 0; i <= n; i++) dp[i][0] = 0;
    for (int j = 0; j <= W; j++) dp[0][j] = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= W; j++) {
            if (j < w[i-1]) {
                dp[i][j] = dp[i-1][j];
            } else {
                int take = dp[i-1][j - w[i-1]] + v[i-1];
                int skip = dp[i-1][j];
                dp[i][j] = take > skip ? take : skip;
            }
        }
    }
    return dp[n][W];
}

时间复杂度 O(n*W)，空间复杂度 O(n*W)。

空间还能优化吗？可以。注意看，dp[i][j] 只依赖 dp[i-1][...]，也就是上一行的数据。所以我们可以只用一维数组：

int knapsack_opt(int W, int n, int w[], int v[]) {
    int dp[W+1];
    for (int j = 0; j <= W; j++) dp[j] = 0;

    for (int i = 0; i < n; i++) {
        // 注意：必须从大到小遍历
        for (int j = W; j >= w[i]; j--) {
            int take = dp[j - w[i]] + v[i];
            if (take > dp[j]) dp[j] = take;
        }
    }
    return dp[W];
}

知识体系总览

下面这张图总结了本章的核心内容：

避坑指南

做 DP 题，有几个坑我反复踩过，分享给大家：

• 初始化没做好：dp[0][0] 或者边界条件没设对，后面全错。我建议先手算几个小例子验证一下。
• 遍历顺序搞反：一维背包必须从大到小，二维无所谓。我曾经在项目里写了个完全背包当 0-1 背包用，结果价值算出来虚高，被测试骂了一顿。
• 状态定义太复杂：能用一维就别用二维，能用二维就别用三维。状态越简单，代码越不容易出错。
• 忘记考虑不选的情况：很多人只想着「拿」，忘了「不拿」也是一种选择。转移方程里一定要比较两种方案。

动态规划不是一蹴而就的。我刚开始学的时候，也是看了很多题、写了很多代码才慢慢找到感觉。别急，多练就好。

---

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