钢条切割问题，DP经典问题

问题描述

输入： 钢条的长度: $n$ 钢条的价格表： $p_i(1\le i\le n)$ 表示长度为$i$ 的钢条的价格

输入： 使得所有钢条总价值最大的切割方案

1、使用递归的解法

int p[MAX]; //价格表 p[0] = 0; // 0长度的钢条价格为0 int r[MAX]; // void solve(int n) // 参数表示钢条的长度 { if(n==0) return 0; // 求最优解 int q = -inf; // 初始化成负无穷，来求最大值 for (int i = 1; i <= n; ++i) { q = max(q, p[i] + solve(n-i)); // i = n; 就是不截取 // i = 1; 就是右端右端截取一个1， 左边剩下0~n-1 求最优 // 只看第一层，这样循环一遍之后就找到了最优的切割值 } return q; }

听到好多次写程序最好不要用递归，说递归写起来简单，运行起来效率很低。这应该是有两个方面的原因吧：

递归效率低是函数调用的开销导致的。 在一个函数调用之前需要做许多工作，比如准备函数内局部变量使用的空间、搞定函数的参数等等，这些事情每次调用函数都需要做，因此会产生额外开销导致递归效率偏低，所以逻辑上开销一致时递归的额外开销会多一些(https://www.zhihu.com/question/35255112)学了动态规划知道，写的一般的递归程序有很多重复的递归调用，如果没有加入备忘的话，就会造成时间复杂度很高，当然这是coder设计算法的问题，我只是想通了为什么自己之前写的递归效率很低。

(什么是尾递归？…

2、 带备忘的递归(自顶向下的递归)

上面那个算法效率低的主要原因是递归向下的过程中，做了计算了太多的重复计算。 所以优化思路就是将计算过的结果保存起来，如果再用它的话，就直接拿出来用。 所以我们保存下来每次递归得到的结果

int r[MAX]; // 初始值都是0 int p[MAX]; // void sovle(int n) { // 如果r[n] 大于0 说明之前已经计算过了，直接返回*********** if(r[n] > 0) return r[n]; // 原来正常的递归。 if (n == 0) return 0; int q = -inf; for (int i = 1; i <= n; ++i) { q = max(q, p[i] + slove(n-i)); } r[n] = q; // 将本次递归的结果保存下来。****************** }

3、自底向上的递推

递推没有递归函数频繁的调用的开销，所以在时间复杂度上通常有更小的系数

int r[MAX]; int p[MAX]; void solve() { r[0] = 0; // 初始化 for(int i = 1; i <= n; ++i){ // 内层循环计算的是[1...j]这个长度的最优值，并且得到了 r[1] r[2] r[j] 的结果 // 当计算i+1时， q = -inf; for (int j = 1; j <= i; ++j) { q = max(q, p[j] + r[i-j]) } r[j] = q; } }

画图理解:

当外层的j运行到a的时候，我们想求出r[j], 就要对[1…j]这一段用 i 进行枚举，求出每种切割的最大值。 相较于之前的无脑递归，我们在求r[j]的时候，r[1…j-1]都是已知的，可以直接用。

图中的

p[i] 表示[1…i] 这一段我们不切割，r[j-i] 表示这一段切割若干次之后最优解，此时我们在求r[j]， 所以小于j的r[j-i]都是之前存下来的。

这是两重循环，所以时间复杂度时$O(n^2)$

4、如何获得最优解的每一段的长度