动态规划算法有什么用？使用C语言编程解决一个实际问题，通俗易懂的学习动态规划法

上一节讨论了程序开发中常用的分治算法，我们总结出使用该算法的其中一条“适用条件”为：原始问题可以拆分为**彼此独立**的子问题。这个条件其实不是使用“分治算法”的必要条件，只不过若子问题有重叠，分治算法会做许多不必要的重复工作，它会反复的求解那些公共的重叠子子问题。因此，如果子问题有重叠，一般不再推荐使用分治算法，可以考虑动态规划。

动态规划的基本思想

动态规划与分治算法相似，都是通过组合子问题的解来获得原始问题的解。只不过与分治算法不同，动态规划特别适合应用于子问题重叠的情况，它对每个子子问题只求解一次，并将解保存，之后求解其他依赖该子子问题的问题时，只需要从保存的结果中找出对应的解即可，这样就避免了反复求解公共的重叠子问题。

由此可以看出，动态规划算法本质上是牺牲部分空间换取时间效率。

钢条切割问题

上面的内容有些枯燥，来看一个实际问题：某公司的主营业务是购买长钢条，将其切割成短钢条出售。已知切割工序本身的成本可以忽略不计，不同长度单位的钢条价格如下表：

长度 i	1	2	3	4	5	6	7	8	9	10	...
价格 p_i	1	5	8	9	10	17	17	20	24	30	...

假设有一段长度为 n 的钢条，问怎样切割才能获得最大的收益？

从钢条价格表可以看出，切割方案都是整数单位切割，对于长度为 n 的钢条，每个单位位置处都有 2 种可能（切，不切），因此总共有 2^n-1 种切割方案，以 n=4 为例，共有以下 8 种切割方案：

容易看出，把长为 4 的钢条切割成 2 个长为 2 的钢条时，能够获得最大的收益为 5+5=10。

暴力穷举法

暴力穷举法的确能够解决问题，但是却不一定能够获得满意的效率。前面提到，对于长度为 n 的钢条有 2^n-1 种切割方案，当 n 足够大时，“指数爆炸效应”很容易让这种解决方案难以在可接受时间内给出结果。

令最优解为收益最大，为了便于讨论，我们使用加法符号“+”表示切割方案，例如 4 = 2+1+1 表示将长度为 4 的钢条切割为三段长分别为 2、1、1的短钢条。因此对于长度为 n 的钢条，假设一个最优解是将钢条切割为 k 段，那么对应的切割方案为：

n = i₁ + i₂ +...+ i_k

最优切割方案确定后，最大的收益也就确定了——直接查表即可，设长度为 n 的钢条对应的最大收益为 mp_n，则：

mp_n = p_i1 + p_i2 +...+ p_ik

一个容易想到的解决方法是：从钢条左边切割下长度为 i 的一段，右边余下的钢条长度为 n-i，左边的钢条不再分割，只对右边的钢条递归继续分割。然后我们让 i 从 1 遍历到 n，也就遍历了所有的分割方案，遍历过程中，保存最大收益，即可得到解，使用数学公式描述这一过程，也即：

mp_n = max(p_i + mp_n-i)，其中 1≤i≤n

现在我们使用C语言编写程序来实现上述算法，使用递归是方便的：

int p[N] = {0,1,5,8,9,10,17,17,20,24,30...
int max_price(int n)
{
    if (0==n)
        return 0;

    int mp = -1, i;
    for (i=1; i<=n; i++) {
        mp = max(mp, p[i]+max_price(n-i));
    }
    return mp;
}

如果读者读过我之前的文章，就应该明白对于C语言中的递归函数，我们更应该从实际需求角度分析它。max_price() 函数接收整数 n，返回长度为 n 的钢条的最大收益。若 n=0，不可能有任何收益，所以直接返回 0。接着，我们定义了变量 mp 用于存放最大收益，因为接下来要取它和分割方案对应的收益（大于0），所以给 mp 赋了负值作为初值。接下来的 for() 循环其实就是在描述公式 mp_n = max(p_i + mp_n-i)。

读者可自行编写 main() 函数测试 max_price()，会发现 max_price(n) 函数的确能够正确计算长度为 n 的钢条最大收益值，例如 max_price(4)=10，max_price(10)=30。

不过解决问题倒不难，难点在于要“有效率”的解决问题，读者可自行测试，随着输入给 max_price() 的参数值逐渐增大，函数执行消耗时间急剧增加。在我的电脑上，max_price(16) 消耗 112ms 的时间，max_price(17) 消耗 332ms 的时间，每将 n 提升 1，函数执行时间就翻一倍多，当 n=30 时，我甚至没有耐心等下去了（我等了10多分钟，函数还没有执行完成）。

可见，暴力穷举法容易想到，也容易实现，但是却往往不能带来足够令人满意的效率。仔细考虑一下，应该不难发现，暴力穷举法的效率之所以如此低下，主要是因为中间产生了很多不必要的重复计算。请看下图：