1 package DynamicProgram; 2  3 import org.junit.Test; 4 import Sort.Array; 5  6 // 算法分析与设计一书中钢条切割问题 7  8 public class CutRod { 9 10     /**11      *              返回包含最优解的数组12      * @param p  p[i]表示长度为i的钢条长度的售价13      * @param n  钢条的长度,单位为英寸14      */15     public int [] bottomUpCutRod(int [] p, int n) {16         // 用来保存当钢条的长度为n时,最优情况下首次切割左边钢条的长度17         int [] array = new int [n + 1];18         array[0] = 0;19         // 长度为i的子问题20         for(int i = 1; i <= n; ++i) {21             // 用来保存最小的代价22             int cost = -1;23             for(int j = 1; j <=i; ++j)24                 // p[j]表示长度为j的钢条所花费的代价25                 // array[i - j]表示长度为i-j的钢条所花费的代价,前面已经计算出来了26                 // 之所以不断的保存cost,是为了计算整趟循环中的最大值27                 cost = Math.max(cost, p[j] + array[i - j]);28             // 将长度为i的子问题的最低花费保存到数组中29             array[i] = cost;30         }31         return array;32         33     }34     35     36     @Test37     public void test(){38         int [] p = {-1, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30};39         int [] array = bottomUpCutRod(p, 10);40         Array.print(array);41     }42 }