第20章 动态规划（上）：从斐波那契到钢条切割

动态规划，简称DP。说实话，很多初学者一听到这个名字就觉得头大。我当年刚接触时也一样，觉得这玩意儿玄乎得很。但做了十几年嵌入式开发，我慢慢发现——DP其实就是一种聪明的穷举。

你想想看，我们平时解决问题，最笨的办法是什么？把所有可能都试一遍。但很多问题里，子问题会重复出现。DP的核心思想就是：把已经算过的结果存起来，下次直接用，别再傻傻地重新算一遍。

DP思想：记住过去，避免重复

动态规划的本质，我总结成一句话：把大问题拆成小问题，把小问题的答案记下来，组合成大问题的答案。

它跟分治有点像，但有个关键区别——分治的子问题通常是独立的，而DP的子问题会重叠。嗯，这个重叠就是DP发挥威力的地方。

说白了，你只要能写出状态转移方程，DP就完成了一半。剩下的就是填表，或者用递归加记忆化。

最优子结构：拆解问题的艺术

什么叫最优子结构？我举个例子你就明白了。

假设你要从北京坐火车去广州，中间经过武汉。如果你走的路线是最短的，那么从北京到武汉这一段，也一定是最短的。为什么？因为如果北京到武汉有更短的路线，那整体路线就可以更短，矛盾了。

这就是最优子结构——全局最优，局部也最优。

我在做嵌入式系统的任务调度时，经常用到这个性质。一个复杂的任务序列，如果整体延迟最小，那么它的每个子序列的延迟也一定是最小的。不然的话，我就可以替换掉那个子序列，让整体更优。

重叠子问题：别做重复劳动

重叠子问题，说白了就是不同的分支会走到同一个子问题上。

拿斐波那契数列来说，你要算F(5)，需要F(4)和F(3)。算F(4)又需要F(3)和F(2)。你看，F(3)被算了两次。如果递归下去，F(2)会被算更多次。

我刚开始学递归时，写了个斐波那契的递归版本，n=40就卡得不行。后来一分析，好家伙，重复计算了指数级的次数。这就是典型的没有处理重叠子问题。

斐波那契数列：DP优化的经典入门

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

我们先看看最朴素的递归写法：

// 朴素递归——性能极差
int fib_recursive(int n) {
    if (n <= 1) return n;
    return fib_recursive(n-1) + fib_recursive(n-2);
}

这个写法的时间复杂度是O(2^n)。n=50时，你的电脑基本就歇菜了。

怎么优化？加个数组做记忆化：

// 记忆化递归——自顶向下
int fib_memo(int n, int* memo) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];  // 已经算过了，直接返回
    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo);
    return memo[n];
}

// 调用时：int memo[100]; memset(memo, -1, sizeof(memo));

这样每个子问题只算一次，时间复杂度降到了O(n)。

但更常见的DP写法是自底向上：

// 自底向上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];
}

还可以进一步优化空间，因为每次只需要前两个值：

// 空间优化版——只保留前两个状态
int fib_optimized(int n) {
    if (n <= 1) return n;
    int prev2 = 0, prev1 = 1, curr;
    for (int i = 2; i <= n; i++) {
        curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return curr;
}

你看，从O(2^n)到O(n)，再到O(1)的空间，这就是DP优化的魅力。

钢条切割问题：真正的DP实战

斐波那契太简单了，我们来看个更实际的问题——钢条切割。

问题描述：你有一根长度为n的钢条，和一个价格表p[i]（i=1..n）。你可以把钢条切成若干段，每段按长度出售。问：怎么切能让总收益最大？

比如价格表是这样的：

长度i	1	2	3	4	5	6	7	8	9	10
价格p[i]	1	5	8	9	10	17	17	20	24	30

长度为4的钢条，怎么切？

• 不切：卖9元
• 切成2+2：卖5+5=10元
• 切成3+1：卖8+1=9元
• 切成1+1+1+1：卖4元

显然，切成2+2最划算。

那长度为n呢？我们需要一个通用的方法。

状态定义：令r[n]表示长度为n的钢条能获得的最大收益。

状态转移方程：r[n] = max(p[i] + r[n-i])，其中1 ≤ i ≤ n。

什么意思？就是第一刀切下长度为i的一段，卖p[i]元，剩下的n-i长度继续按最优方式切割，收益是r[n-i]。我们遍历所有可能的i，取最大值。

来看代码实现：

// 自底向上DP——钢条切割
int cut_rod(int* p, int n) {
    int r[n+1];
    r[0] = 0;  // 长度为0，收益为0
    
    for (int j = 1; j <= n; j++) {
        int max_val = -1;
        for (int i = 1; i <= j; i++) {
            int val = p[i] + r[j-i];
            if (val > max_val) {
                max_val = val;
            }
        }
        r[j] = max_val;
    }
    return r[n];
}

这个算法的时间复杂度是O(n²)。对于n=1000以内的场景，完全够用。

如果我们还想知道具体怎么切的，可以加一个记录数组：

// 带切割方案的钢条切割
void cut_rod_with_solution(int* p, int n) {
    int r[n+1], s[n+1];  // s记录第一刀切多长
    r[0] = 0;
    
    for (int j = 1; j <= n; j++) {
        int max_val = -1;
        for (int i = 1; i <= j; i++) {
            int val = p[i] + r[j-i];
            if (val > max_val) {
                max_val = val;
                s[j] = i;  // 记录最优的第一刀长度
            }
        }
        r[j] = max_val;
    }
    
    // 输出切割方案
    printf("最大收益：%d\n", r[n]);
    printf("切割方案：");
    int len = n;
    while (len > 0) {
        printf("%d ", s[len]);
        len -= s[len];
    }
    printf("\n");
}

这样，你不仅知道最大收益是多少，还知道具体怎么切。

DP的核心流程总结

做DP题，我一般按这个步骤来：

1. 定义状态：dp[i]或dp[i][j]表示什么？想清楚再动手。
2. 找转移方程：当前状态怎么从前面的状态推出来？
3. 初始化：边界条件是什么？比如dp[0]=0。
4. 确定遍历顺序：是从小到大，还是从大到小？
5. 优化空间：能不能只用几个变量代替数组？

这五步走下来，大部分DP问题都能解决。

好了，这一章我们聊了DP的核心思想，用斐波那契和钢条切割两个例子做了实战。下一章我们会继续深入，看看更复杂的DP问题——比如背包问题、最长公共子序列。到时候你会发现，只要掌握了今天讲的这套方法论，再难的DP也能拆解成简单的状态转移。

---

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