1.代码

递归（Java实现）：

//递归
public static int cutRodRecursive(int[] prices, int n) {// 边界条件if (n <= 0) {return 0;}int maxPrice = -1;// 遍历所有可能的切割方案，选择最优解for (int i = 0; i < n; i++) {maxPrice = Math.max(maxPrice, prices[i] + cutRodRecursive(prices, n-i-1));}return maxPrice;
}
​

备忘录（记忆化）和自顶向下的动态规划算法切割钢条的示例代码（Java实现）：

public static int cutRod(int[] prices, int n) {// 创建一个备忘录，用于存储已经计算过的结果int[] memo = new int[n + 1];Arrays.fill(memo, -1);return cutRodMemo(prices, n, memo);
}
​
public static int cutRodMemo(int[] prices, int n, int[] memo) {// 边界条件if (n <= 0) {return 0;}// 如果已经计算过，直接返回结果if (memo[n] != -1) {return memo[n];}int maxPrice = -1;// 遍历所有可能的切割方案，选择最优解for (int i = 0; i < n; i++) {maxPrice = Math.max(maxPrice, prices[i] + cutRodMemo(prices, n-i-1, memo));}// 将计算结果保存到备忘录中memo[n] = maxPrice;return maxPrice;
}
​

自底向上的动态规划算法切割钢条的示例代码（Java实现）：

‍

获取对应的钢铁

package collection;
​
public class CutRod {public static int[] cutRod(int[] p, int n) {//每一段最大的数据int[] r = new int[n + 1];//存储第一段int[] s = new int[n + 1];r[0] = 0;for (int j = 1; j <= n; j++) {int q = Integer.MIN_VALUE;for (int i = 1; i <= j; i++) {
//                因为 j = j +i -i;
​
//                第二次遍历的时候q = p[i] + r[j - i];来获取最大的值,if (p[i] + r[j - i] > q) {q = p[i] + r[j - i];s[j] = i;}}r[j] = q;}int[] result = new int[n + 1];while (n > 0) {System.out.println(n);System.out.println(s[n]);result[s[n]]++;n -= s[n];}return result;}
​public static void main(String[] args) {int[] p = {0, 1, 5, 8, 9, 10, 17, 17, 20,24,30};int[] result = cutRod(p, 7);
//        System.out.println(Arrays.toString(result));}
}
​

2.动态规划中的自顶向下法和 自底向上法

第一种方法称为带备忘的自顶向下法(top-downwith memoization沪。此方法仍按自然的递 归形式编写过程，但过程会保存每个子问题的解（通常保存在一个数组或散列表中）。当需要一个 子问题的解时，过程首先检查是否已经保存过此解。如果是，则直接返回保存的值，从而节省了 计算时间；否则，按通常方式计算这个子问题。我们称这个递归过程是带备忘的(memoized), 因为它“记住”了之前已经计算出的结果。

第二种方法称为自底向上法(bottom-upmethod)。这种方法一般需要恰当定义子问题”规模"的概念，使得任何子问题的求解都只依赖于“更小的“子问题的求解。因而我们可以将子问题按规模排序，按由小至大的顺序进行求解。当求解某个子问题时，它所依赖的那些更小的子间题都已求解完毕，结果已经保存。每个子问题只需求解一次，当我们求解它（也是第一次遇到它）时，它的所有前提子问题都已求解完成。

3.总结

求最大值 可以通过for +递归+ Math.max +外层变量 来解决 ,再考虑一下边界条件.

自底向上, 是一种有序的计算,因为在计算3之前 1和2 都是已经被计算了

4.其他自行看书

‍