钢条切割-递归

题的描述就不写了。

本篇是《算法导论》中钢条切割的递归实现（实际生产中效率很低，复杂度是指数增长的，使用线性规划可以将复杂度由指数增长优化为线性增长），以后会补上线性规划实现。

分治法适用情景：一个大问题可分割成2份相互独立的子问题
线性规划适用场景：一个大问题分割成的子问题需要子子问题的结果

代码中p数组是长度 1-9 对应的价值，p[0]=0。

递归一般都是根据数学归纳法实现的。
假设第i次最优解为r(i-1),则第i次的最优解可能为r(i-1)+p[1]，也可能是r(i-2)+p[2]，一般解可以用r(n-i)+p[i]表示，需要比较所有解中最大的值。
程序之前先考虑几个问题：
1、 怎么覆盖所有可能的解
2、 递归调用重复计算的位置在哪
3、 怎么知道取到最优解时候的切割方式

public void test(){
    int [] p = {0, 1, 5, 8, 9, 10, 17, 17, 20, 24};
    cut(p, 4);
}

    public int cut(int[] p, int n){
        if (n == 0){
            return 0;
        }
        int q = -1;
        for (int i = 1;i <= n;i++){
//max 方法是返回2个值的最大值
            q=max(q, p[i] + cut(p, n - i));
            if (i==n){
//当 i==n 的时候就会进入上面的if(n == 0)返回 然后通过max方法获取最大值
                System.out.println("最优解： " + q);
            }

        }
        return q;
    }
public int max(int a, int b){
        return a > b ? a : b;
}

接下来分析一下程序思路和执行顺序。
程序需要如下：（括号内有的是对前一句话的解释）
1、递归都要有的出口
2、分析q=max(q, p[i] + cut(p, n - i));
这句是取q和第i个p对应的价值加上第n-i的最优解（递归调用的）
因为有外层for循环，i的值会从1增加到n（这样就可以表示所有的解）
执行顺序：
1、for循环是什么时候执行的
2、递归执行的顺序

cut(p, 4)
  cut(p, 3)
    cut(p, 2)
      cut(p, 1)   
        cut(p, 0)   //返回cut(p, 0) 

cut(p, 0)的顺序
1  cut(p, n - i)=0  因为n-i==0 然后会返回 0
2  然后和p[i]相加  后与q求最大值 （最大值是p[i]+0），   所以 ，q = 1；
3  获取完q（最优解）之后 ， for循环执行（也就是1的问题） 
for循环会把cut(p, i)的所有情况都会递归（覆盖n=i时的所有解）。
不过在for循环的时候又会重新递归调用已经计算过的解。

上面只解释了最外层的递归
cut(p， 0)的结果返回之后 ，cut(p, 1)会获取到这个返回值 （也就是最外层结果返回，然后返回到递归的上一层， 并给上一层提供结果，这样一直到cut(p, 4)）

n=4时cut(p, n)调用过程

怎么理解这个图
图中圆圈中的标号就是对应的cut(p, i)
n=4 i=1 调用了cut(p, 3) cut(p, 2) cut(p, 1) cut(p, 0) (对应的是4-3-2-1-0 纵向)
n=4 for循环对应的是 i=3 i=2 i=1 i=0(横向)