15. 1 钢条切割-Toy模板网

这篇具有很好参考价值的文章主要介绍了15. 1 钢条切割。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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实现）：

‍文章来源地址https://www.toymoban.com/news/detail-422276.html

获取对应的钢铁

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