数据结构与算法系列源代码：https://github.com/ThinerZQ/AllAlgorithmInJava
本文源代码：https://github.com/ThinerZQ/AllAlgorithmInJava/blob/master/src/main/java/com/zq/algorithm/dynamicprogrammin/SteelBar.java
如果代码链接失效了，麻烦评论给我。
动态规划与分治法相似，都是通过组合子问题的解来求解原问题。
分治法将问题划分为不互相交子问题，递归的求解子问题，再将他们组合起来，求出原问题的解。
与之相反，动态规划应用于子问题重叠的情况，即不同的子问题具有公共的 子子问题。这种情况下分治法会重复的求解那些公共的子子问题。而动态规划算法对每个子子问题只求解一次，将其存放在某一个表格中，无需每次求解一个子子问题时都重新计算，避免了不必要的计算工作，特别是当问题规模比较大的时候，在时间上有显著的区别
动态规划用来求解最优化问题。这类问题可以有很多可行的解，每个解都有一个值，我们希望需找具有最优值（最大或最小）的解。当然可能同时存在多个最优解（同时最大，或同时最小），动态规划只要求找到其中一个就好了。
这里我们用算法导论里面的钢条切割为例子。
切钢条：假如Serling公司出售一段长度为 i 英寸的钢条的价格为 pi( i =1,2,3,4…单位问美元)。钢条的长度为整英寸。
下表是一个价格表。
| 长度i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 价格pi | 1 | 5 | 8 | 9 | 10 | 17 | 17 | 20 | 24 |
假设Serling公司进了一批长度为10的钢条，那么怎么切割才能使利益最大呢，长度为 9 , 8 呢？
对于上述价格表样例，我们可以观察出所有最优收益值Ri及对应的最优解方案：
| 最优值 | 切割方案 |
|---|---|
| R1 = 1 | 切割方案1 = 1（无切割） |
| R2 = 5 | 切割方案2 = 2（无切割） |
| R3 = 8 | 切割方案3 = 3（无切割） |
| R4 = 10 | 切割方案4 = 2 + 2 |
| R5 = 13 | 切割方案5 = 2 + 3 |
| R6 = 17 | 切割方案6 = 6（无切割） |
| R7 = 18 | 切割方案7 = 1 + 6或7 = 2 + 2 + 3 |
| R8 = 22 | 切割方案8 = 2 + 6 |
| R9 = 25 | 切割方案9 = 3 + 6 |
| R10 = 30 | 切割方案10 = 10（无切割） |
更一般地，对于Rn（n >= 1），我们可以用更短的钢条的最优切割收益来描述它：
Rn = max(Pn, R1 + Rn-1, R2 + Rn-2,…,Rn-1 + R1)
首先将钢条切割为长度为i和n - i两段，接着求解这两段的最优切割收益Ri和Rn - i（每种方案的最优收益为两段的最优收益之和），由于无法预知哪种方案会获得最优收益，我们必须考察所有可能的i，选取其中收益最大者。如果直接出售原钢条会获得最大收益，我们当然可以选择不做任何切割。
注意到，为了求解规模为n的原问题，我们先求解形式完全一样，但是规模更小的子问题。当完成首次切割之后，我们将两段钢条看成两个同等的钢条切割问题实例，通过组合两个问题的最优解，并在所有可能的两段切割方案中选择组合收益最大值，构成原问题的最优解，我们称这样的问题满足最优子结构性质：问题的最优解是由相关子问题的最优解组和而成的，这些子问题可以独立求解。
分析到这里，假设现在出售10英寸的钢条，应该怎么切割呢？为了方便分析，我们使用钢条长度=4来分析问题
1、解法：
1.1 递归法：
/**
* 递归方法，时间复杂度为O（2的N次方），因为考察了 2的N-1次方种可能
* @param p，钢条的价格数组，
* @param n，钢条的长度，这里的划分是以 1 为单位
* @return 最大收益
*/
public int cut_rod(int[] p,int n){
//递归出口，n=0，不用切割了。
if ( n==){
System.out.println("调用子问题规模：0");
return ;
}
// q 是最大值，初始值设为为一个负值，
int q=-;
//对于每一次递归调用，都会求1..n之间的最优质，然后返回给上一层
for (int i=;i<=n;i++){
//当前长度为 n 的切割收益的最大值，是当前的 q .和p[i]+cut_rod(p,n-i)中的最大值，循环中时不断改变q值的，
System.out.println("调用子问题规模："+n);
q=max(q,p[i]+cut_rod(p,n-i));
if (i==n){
System.out.println("子问题规模为 "+n+" 的最优值 = "+q);
}
}
System.out.println("回到第："+(n+)+"层");
System.out.println();
return q;
}
public int max(int a,int b){
return a>b?a:b;
}
1.1.1 分析：
上面代码的递归中，始终会重复执行太多相同的操作，例如cut_rod(p,4)会递归调用cut_rod(p,3),cut_rod(p,2),cut_rod(p,1),cut_rod(p,0)，当调用cut_rod(p,3) 的时候，又会递归调用cut_rod(p,2),…cut_rod(p,1)……..。
1.1.2 程序输出结果：
1.1.3 程序递归分析
………..如此多的重复递归是没有必要的，这也是动态规划所要处理的问题。
怎么避免重复调用呢？？
动态规划的做法是，将每一次求得的cut_rod(p,i)的最优值保存在一个表（数组）里面，每次需要使用的时候，不用再递归调用了，直接使用就好了。
1.2 动态规划——>带备忘的自顶向下法:
/**
* 动态规划方法
* 带备忘的自顶向下法
* @param p，钢条的价格数组，
* @param n，钢条的长度，这里的划分是以 1 为单位
* @return 最大收益
*/
public int memoized_cut_rod(int[] p,int n){
//一个数组，用r[i] 来保存 钢条长度为 i 的时候的最优值，初始值赋为 -1.一个负值就行。
int[] r= new int[n+];
for (int i=;i<r.length;i++){
r[i]=-;
}
//调用递归的那个方法，返回长度为 n的最优值。
return memoized_cut_aux(p,n,r);
}
/**
*
* @param p，钢条的价格数组，
* @param n，钢条的长度，这里的划分是以 1 为单位
* @param r 保存中间值的数组
* @return 最大收益
*/
public int memoized_cut_aux(int[] p,int n,int[] r){
//递归出口，如果r[n] >0,表明，长度为 n 的钢条的最优值已经存在了。不用递归了，直接返回这个最优值，这里必须是r[n]>=0,因为r[0]是等于0的，
if (r[n]>=){
System.out.println();
System.out.print(" ------直接返回r[" + n + "] = " + r[n] );
return r[n];
}
//设置零时变量 q 最为最大值
int q=-;
//刚进入递归的时候，刚开始一路调用下来，必然是从这个口出去。
if (n==){
q=;
System.out.print(" 调用 n ="+q + " 第一次保存r[0]的值：" + q);
}else {
//递归调用，求解最大值。
System.out.println(" 调用 n ="+n);
for (int i=;i<=n;i++){
q = max(q,p[i]+memoized_cut_aux(p,n-i,r));
System.out.print(" 开始回溯到n="+n);
if (i==n){
System.out.println();
}
// System.out.println();
}
}
System.out.println();
//将每一次求的长度为 n 的最优值保存在数组 r 里面
r[n]=q;
//返回最大值
if (n==r.length-){
System.out.println("程序结束，返回r["+n+"]="+r[n]);
}
return q;
}
1.2.1 分析：
上面使用自顶向下的方法，求解问题，就像深度优先搜索二叉树一样。具体分析见下图
1.2.2 程序输出结果：
1.2.3 程序递归分析：
1.3 动态规划——>自底向上法：
/**
* 动态规划，自底向上求解。
* @param p，钢条的价格数组，
* @param n，钢条的长度，这里的划分是以 1 为单位
* @return 最大收益
*/
public int bottomUpCutRod(int[] p,int n){
//一个数组，用r[i] 来保存 钢条长度为 i 的时候的最优值，初始值赋为 0.
int[] r= new int[n+];
for (int i=;i<r.length;i++){
r[i]=;
}
//循环,外层依次求解 1....n的最优值
for (int j=;j<=n;j++){
int q=-;
//内层，依次在 1 .. j 中求出最大值，
//例如
// 当 j =1 的时候，q=max(q,p[1]+r[0]) .求的r[1]的最优值
// 当 j =2 的时候，q=max(q,p[1]+r[1])，然后再是 q=max(q,p[2]+r[0]) ，求的r[2]的最优值
// ... 以此类推
for (int i=;i<=j;i++){
q=max(q,p[i]+r[j-i]);
}
//记录 j 的最优值
r[j]=q;
}
//最终返回 n 的最优值
return r[n];
}
1.3.1 分析：
这个方法是动态规划最佳方法，具体见后面的总结
1.3.2 程序结果：
1.3.3 程序分析：
自底向上的方法，不必进行递归调用，而是直接访问数组元素r[j-i]来获得规模为j-i的子问题的解。同时也将规模为j的解存入r[j]。就像上图一样，r[0]的解是0，r[1]的解依靠r[1] ，r[2]的解依靠r[0]和r[1]…..r[4]的解依靠r[0]和r[1],r[2],和r[3].
上面只是求出了，钢条长度为 i 的最优值，那么怎么切割呢？下面砸门来看看
1.4 求解切割方案
直接上代码，
extended_button_up_cut_rod
函数和自底向上求解最优值的函数是一样的，不同点就是加入了一个保存切割方案的数组s，每次找到最优值的时候，记录切割方案。
/**
* 求解最优值和组合方案
* @param p 价格表
* @param n 钢条长度
* @param r 最优值数组，
* @param s 切割方案数组
*/
public void extended_button_up_cut_rod(int[] p,int n,int[] r,int[] s){
//循环,外层依次求解 1....n的最优值
for (int j=;j<=n;j++){
int q=-;
//内层，依次在 1 .. j 中求出最大值，
//例如
// 当 j =1 的时候，q=max(q,p[1]+r[0]) .求的r[1]的最优值
// 当 j =2 的时候，q=max(q,p[1]+r[1])，然后再是 q=max(q,p[2]+r[0]) ，求的r[2]的最优值
// ... 以此类推
for (int i=;i<=j;i++){
if (q<p[i]+r[j-i]){
q=p[i]+r[j-i];
//记录长度为 j 的钢条 第一下开始切割的位置 i .
s[j]=i;
}
}
//记录 j 的最优值
r[j]=q;
}
}
/**
* 输出最优值和切割方案的函数
* @param p 价格表
* @param n 钢条长度
*/
public void print_cut_rod_solution(int[] p,int n){
//一个数组，用r[i] 来保存 钢条长度为 i 的时候的最优值，初始值赋为 0.
int[] r= new int[n+];
for (int i=;i<r.length;i++){
r[i]=;
}
int[] s = new int[n+];
for (int i=;i<r.length;i++){
s[i]=;
}
//调用求最优值和方案的函数
extended_button_up_cut_rod(p,n,r,s);
System.out.print("n="+n+" 的最优值为："+r[n]+" , 切割方案为：");
//当 n>0 的时候，表明还有长度需要切割，哪怕做0切割
while (n>){
//输出，组合方案
System.out.print(s[n] + "+");
//改变 n 的值，n=s[n]表示 已经切割下了s[n]那么长，剩下的要怎么切割
n=n-s[n];
}
}
1.4.1 程序结果：
可以参考上面给出的表格中的数据
1.4总结：
第一种直接的自顶向下的递归方法，没有考虑子问题重叠问题，时间复杂度为指数级问题规模稍微大一点，比如（n=30）,时间复杂度就不能忍受了。
第二种自上而下的带备忘录递归方法，考虑了子问题重叠问题，利用空间来保存求得的结果，时间复杂度为o(n^2)，效果较好。
第三种自下而上的方法，很自然的考虑了子问题重叠问题，时间复杂度为o(n^2)，没有频繁的递归调用的开销，这种方法具有更下的系数。更好。和第二种方法空间复杂度一样都是O(n)