钢条切割-自底向上

自底向上是从第1-n次的解都保存在数组中，比直接递归的效率高，而且思路也不复杂
只需要想一下怎么存储从1-n 最优解的值
比如取到了最优解 r[0] r[1] r[2] r[3]
那么r[4] 最优解就在 r[3]+p[1] 、r[2]+r[2]、r[4]（p[4]）中,就是现在只考虑横向（递归实现的那张图）
纵向递归的值（只存最优解）都会被存在数组中

int[] r = new int[5];
    @Test
    public void test(){
        int [] p = {0, 1, 5, 8, 9, 10, 17, 17, 20, 24};
        System.out.println(cut_rod(p, 4));
    }
    public int cut_rod(int[] p, int n){
//      p[0] = 0;
//外层for控制整体次数    （也就是可以获得第i次的最优解）
        for (int i = 1; i <= n; i++) {
            int q = -1;
//内层控制  第j次所有解（覆盖第j次所有的解）然后比较最优  保存q 然后下次循环和q比较最后得出最优跳出循环 
            for (int j = 1; j <= i; j++) {
//这一步和递归差不多 不过这里不是递归调用  而是直接获取上次的解（不一定是最优解）
                q = max(q, p[j] + r[i - j]);
            }
//第i次的解存在数组中
            r[i] = q;
        }
        
        return r[n];
    }
    private int max(int m, int n) {
        return m > n ? m : n;
    }