【DP1】钢条分割详解

[DP]
原文再续书接上一回，上一篇文章的背包讲的有点过于狭隘，我就某一类问题解释一种算法的思想：动态规划(Dynamic Programming)。简称DP。
我们在生活中不免会遇到一类问题，求什么什么的最大，什么什么的最小。在这类问题中，如果有算法基础的同学可能会知道贪心算法，但是贪心算法是无法在所有的情况下保证最优解的，而DP是可以的。
那么DP是什么？我们直接用一道题目来举例子去解释DP。
这里采用的例子引用自CLRS中的钢条分割问题。我只做一个概括性复述。有兴趣的同学可以去看看原著（这里强力吹一波CLRS，如果能够静下心来看，这本书还是相当的不错。）
长度为n英寸的钢条，若给出一个数组p[n]，该数组是指不同长度下钢条所能给出的价格，例如：

有一种很蠢但是很好理解的算法，就是我一共有n个元素(长度为n的钢条分割最小单元为1的情况下，我最多有n个元素)。所以我一共有2^(n-1)个方案（含重复的）我每个方案都算一个价格出来，在其中取最大值不就可以了吗？
当然可以，但是开销也是蹭蹭蹭地往上跑。

我们先提出一种递归的解法。
我们来分析最初的情况，我们从最左端开始看
我们在一开始，在i=1的情况下，我们可以选择切/不切
注意：这里是整个算法的关键
如图：

我们把情况变成正常情况，

我们就有，在k处，选择切还是不选择切，设，我们的最优解一共把他切成了K段，那我们就有利润=P[I1] +P[I2] +P[I3]+…+P[Ik]我们这里的I k指的是第k段的长度。
我们光这样看好像觉得有点不知所措。我怎么知道他在哪切的？我怎么知道为什么这样切就是最优解？
那我们就来求这个切的位置
我们的基础方法就是把我们每次的切点。都表示，我要将左边单独看成一段，也就是说，我在这里切了，左边的长度就是我卖出去钢条的长度，那么在此基础上，我们就有：
我只需要比较切了跟不切的大小就可了，我在切/不切之间取最大值，我们就知道了。
打个比方，我最初我要比较i=1的时候我在想要不要切，那我们切不切的标准是为了让我们最后的值是最优解嘛，那很简单，我直接比较我切的时候和不切的时候哪个值更大不就完了？
递归代码如下

#include<iostream>
using namespace std;
int max(int a, int b) {
	return a > b ? a : b;
}
int value(int valuesTable[], int n) {
	if (n == 0)return 0;
	int q = -1;
	for (int i = 1; i <= n; i++) {
		q = max(q, valuesTable[i] + value(valuesTable, n - i));
	}
	return q;
}
int main() {
	int lengthOfSteel;
	while (cin >> lengthOfSteel) {
		int* valuesTable;
		valuesTable = new int[lengthOfSteel + 1];
		for (int count = 1; count <= lengthOfSteel; count++)cin >> valuesTable[count];
		//input

		cout << "Output is " << value(valuesTable, lengthOfSteel)<<endl;
	}
}

当我们用max_values_length表示这个长度能拿到的最大利益时，我们就有一个推导方程。（不是什么高深的公式，就是从上述推导出来的结论)
我们这里的关键在于

q = max(q, valuesTable[i] + value(valuesTable, n - i));

我们把钢铁剩余部分的价值（减去前i长度后的长度的价值）交给递归的程序去计算，我们不需要手动去算，这就是递归代码的优势–容易理解，且容易实现。
可是
这一段代码不比我们一开始罗列出所有的方案，然后找最大值要好，为什么？我们画树状图进行分析

我们从树状图中可以看到，在这样递归的运算中，我们每一次求第n项，必须访问1到n-项。就是说，第n项的值取决于前n-1项的值，而在这个过程中，我们会反复求解于底层的某一个数。例如在该图中，1就被访问了3次（图中只画出了三次，但其实2扩展之后还会再访问一次了）。也就是说0会被访问很多次。

这样其实增加了很多的开销，我们DP的思想就是在递归程序中每次取值的时候我们都能有一个地址，让我能够判断这个值是否被算过，如果被算过了那么我们就直接调用就可以了，而不是像传统的递归程序需要重新计算一次。如果没算过，那就算一次之后进行存储就好了。以便下一次调用的时候能够直接通过DP_Table数组进行访问就可以了(DP_Table就是一个动态规划表，用来存储每一个状态的值。避免过度的运算)

我们先实现自顶向下的带备忘的递归写法。

#include<iostream>
using namespace std;
int max(int a, int b) {
	return a > b ? a : b;
}
int value(int valuesTable[], int n,int DP_Table[]) {
	if (DP_Table[n] >= 0)return DP_Table[n];
	else {
		int temp = -1;
		for (int i = 1; i  <= n; i++) {
			temp = max(temp, valuesTable[i] + value(valuesTable, n - i, DP_Table));
		}
		DP_Table[n] = temp;
		return temp;
	}
}
int main() {
	int lengthOfSteel;
	while (cin >> lengthOfSteel) {
		int* valuesTable;
		valuesTable = new int[lengthOfSteel + 1];
		int* DP_table = new int[lengthOfSteel + 1];
		memset(DP_table, -1, lengthOfSteel + 1);
		DP_table[0] = 0;
		for (int count = 1; count <= lengthOfSteel; count++)cin >> valuesTable[count];
		//input

		cout << "Output is " << value(valuesTable, lengthOfSteel,DP_table)<<endl;
	}
}

如果此时你理解了不带备忘效果的递归代码，那么我相信这段代码你看起来也不会吃力。

尽管带备忘效果的递归代码已经能够满足我们的时间复杂度的要求了，但是我们的计算机是非常不愿意跑你的递归代码的，当n的数量级上去了，压栈的时间也不能忽略，还有可能会发生把栈压爆而非正常终止的情况。那么我们就顺顺计算机的意愿：写一个自底向上的迭代程序就能避免这方面的问题了。
为了方便理解，我先贴代码再解释

#include<iostream>
using namespace std;
int max(int a, int b) {
	return a > b ? a : b;
}
int value(int valuesTable[], int n,int DP_Table[]) {
	DP_Table[0] = 0;
	int temp = -1;
	for (int i = 1; i <= n; i++) {
		temp = -1;
		for (int j = 1; j <= i; j++) {
			temp = max(temp, valuesTable[j] + DP_Table[i - j]);
		}
		DP_Table[i] = temp;
	}
	return DP_Table[n];
}
int main() {
	int lengthOfSteel;
	while (cin >> lengthOfSteel) {
		int* valuesTable;
		valuesTable = new int[lengthOfSteel + 1];
		int* DP_table = new int[lengthOfSteel + 1];
		for (int count = 1; count <= lengthOfSteel; count++)cin >> valuesTable[count];
		//input
		cout << value(valuesTable, lengthOfSteel, DP_table)<<endl;
		
	}
}

主函数中的代码就没什么好说了，就都是一个调用Solution的过程，这里主要说一下value函数
在Value函数中，我每一次的循环开始我都定义一个临时变量temp，用来记录该切点左边一段的钢条能卖最贵是多少，并把它放在DP数组的对应索引下，而我们每次在最外层循环结束，都能依次得到，前面长度为i的钢条最贵能卖多少钱。而我们后面的最优解又只依赖着前面的各个最优解的值（注意这里的只，这决定了没有后效性的问题，后文会对后效性进行详解），所以就能算出整体的最优解，因为我们能保证每一个局部都是最优解，自然出来的结果也是最优解

好了，我们三段代码，三种方法解决了这个钢条切割的问题，我们来总结一下吧。我们解决问题的顺序依次是，我们要找到一个能够解决该问题的递归代码。而该递归代码依赖着我们的分段分析，这也称为最优子结构，在钢条切割问题上，我们的最优子结构就是，我们要不要切，我们切了之后是分成两段多长的钢条，对于切下来的部分可以直接转换成价值，而剩下的钢条可以重新看成一个新的钢条切割问题，只是此时的sum不再是0，长度变成n-i。转换成伪码的形式就是

CUT-ROD(p,n)
	if(n==0)
		return 0
	for(i =1 -> n)
		q=max { q,p[i]+CUT-ROD(p,n-i) }
	return q;

而在这个钢条分割问题中，我们显然发现他们除了存在一种最优子结构以外，还会因为递归的代码而产生一种重叠子问题(Overlapped Subproblem)，而顺口提一嘴上面提到的无后效性，这直接决定了我们能不能用动态规划算法求解某问题，如果一个问题不存在无后效性，例如我们图论方面的部分问题。
在我后续关于DP的文章中还会多次重复地提到
1.重叠子问题
2.无后效性
3.最优子结构
这三者。

感谢你能看到这里。