递归实现钢条切割问题（Java版）

钢条切割问题递归有两种思想：

1.切割一刀分别获取两两边的最优解相加，获取两两相加的最优解和不切割的比较这样就可以得出可以分割的最大价值。

公式：r(n)=max(p[n] , r(1)+r(n-1) , r(2)+r(n-2) ,……，r(n-1)+r1)

public static int cut(int[] p, int value) {
        if (value == 0) {
            return 0;
        } else {
            int result = 0;
            //防止越界，如果钢条长度超过了数组的长度就让不分的价值为-1
            if (value > p.length - 1) {
                result = -1;
            } else {
                result = p[value];
            }

            for (int i = 1; i < value; i++) {
                result = Math.max(result, cut(p, value - i) + cut(p, i));
            }
            return result;
        }
    }

2.也是切割一刀，让左边的不在分割，左边从价值表中的钢条长度一个个遍历上去，然后求出右边最大解。

一开始很懵，后面经历了在纸上画图，大致也明白了，我们最后切割出来的最优方案肯定有价值表中的其中一段， 那么我们就分别用价值表中的一段去和右边的最优的值相加，最后再比较一下谁的最大就ok了，一开始蒙的地方是，左边是3，那3也可以分割成1和2，或2和1，为啥左边不分隔，右边分割也可以计算出来，左边都不是最优值。其实仔细想想也能想明白，我们用1当左边钢条的时候我们其实就计算过了1开始的这种可能性了，以此类推，2开头的可能性我们也在2在左边时候计算过了，其实所有的情况都是可以遍历到的。

公式：r(n)=max(p[i]+r(n-i))

public static int cut1(int[] p, int value) {
        if (value == 0) {
            return 0;
        } else {
            int result = 0;
            if (value > p.length - 1) {
                result = -1;
            } else {
                result = p[value];
            }

            for (int i = 1; i < value; i++) {
                result = Math.max(result, cut1(p, value - i) + p[i]);
                if (i > p.length - 1) {
                    break;
                }
            }
            return result;
        }
    }

private static int[] p = {0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30};

    public static void main(String[] args) {
        System.out.println(cut1(p, 11));
    }