切割棒以获得最大利润

给定一根长度为 n 英寸的长度和长度为 m 的数组，其中包含所有尺寸小于 n 的尺寸的价格。我们必须找到通过切割杆和销售件而获得的最大值。例如，如果杆的长度是 8 并且不同部件的值如下给出，则最大可获得值是 22 。

       +---+---+---+---+---+---+---+---+
 (price)| 1 | 5 | 8 | 9 | 10| 17| 17| 20|
        +---+---+---+---+---+---+---+---+

我们将使用 2D 数组 dp [m] [n + 1] ，其中 n 是杆的长度，m 是价格数组的长度。对于我们的例子，我们需要 dp [8] [9] 。这里 dp [i] [j] 将通过销售长度为 j 的杆来表示最高价格。我们可以将长度 j 的最大值作为一个整体，或者我们可以打破长度以最大化利润。

首先，对于第 0 列，它不会贡献任何内容，因此将所有值标记为 0.因此第 0 列的所有值都将为 0.对于 dp [0] [1] ，我们可以获得的最大值是多少卖长杆 1.长度为 1.对于长度为 2 dp [0] [2]的杆，我们可以得到 2（1 + 1）。这一直持续到 dp [0] [8] 。所以在第一次迭代之后我们的 dp []数组看起来像。

      +---+---+---+---+---+---+---+---+---+
 (price)| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
        +---+---+---+---+---+---+---+---+---+
  (1) 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 9 |
        +---+---+---+---+---+---+---+---+---+
  (5) 2 | 0 |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+
  (8) 3 | 0 |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+
  (9) 4 | 0 |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+
 (10) 5 | 0 |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+
 (17) 6 | 0 |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+
 (17) 7 | 0 |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+
 (20) 8 | 0 |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+

对于 **dp [2] [2]，**我们要问自己，如果我将杆分成两块（1,1）或整个杆（长度= 2），我能得到的最好的是什么。我们可以看到如果我将杆分成两块，我可以获得的最大利润是 2，如果我有杆作为一个整体，我可以卖它为 5.在第二次迭代之后，dp []数组看起来像：

     +---+---+---+---+---+---+---+---+---+
 (price)| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
        +---+---+---+---+---+---+---+---+---+
  (1) 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 9 |
        +---+---+---+---+---+---+---+---+---+
  (5) 2 | 0 | 1 | 5 | 6 | 10| 11| 15| 16| 20|
        +---+---+---+---+---+---+---+---+---+
  (8) 3 | 0 |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+
  (9) 4 | 0 |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+
 (10) 5 | 0 |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+
 (17) 6 | 0 |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+
 (17) 7 | 0 |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+
 (20) 8 | 0 |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+ 

所以要计算 dp [i] [j]，我们的公式将如下所示：

if j>=i
    dp[i][j] = Max(dp[i-1][j], price[i]+arr[i][j-i]);
else
    dp[i][j] = dp[i-1][j];

在最后一次迭代之后，我们的 dp []数组看起来像

       +---+---+---+---+---+---+---+---+---+
 (price)| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
        +---+---+---+---+---+---+---+---+---+
  (1) 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 9 |
        +---+---+---+---+---+---+---+---+---+
  (5) 2 | 0 | 1 | 5 | 6 | 10| 11| 15| 16| 20|
        +---+---+---+---+---+---+---+---+---+
  (8) 3 | 0 | 1 | 5 | 8 | 10| 13| 16| 18| 21|
        +---+---+---+---+---+---+---+---+---+
  (9) 4 | 0 | 1 | 5 | 8 | 10| 13| 16| 18| 21|
        +---+---+---+---+---+---+---+---+---+
 (10) 5 | 0 | 1 | 5 | 8 | 10| 13| 16| 18| 21|
        +---+---+---+---+---+---+---+---+---+
 (17) 6 | 0 | 1 | 5 | 8 | 10| 13| 17| 18| 22|
        +---+---+---+---+---+---+---+---+---+
 (17) 7 | 0 | 1 | 5 | 8 | 10| 13| 17| 18| 22|
        +---+---+---+---+---+---+---+---+---+
 (20) 8 | 0 | 1 | 5 | 8 | 10| 13| 17| 18| 22|
        +---+---+---+---+---+---+---+---+---+

我们将得到 dp [n] [m + 1]的结果。

用 Java 实现

public int getMaximumPrice(int price[],int n){
        int arr[][] = new int[n][price.length+1];
        
        for(int i=0;i<n;i++){
            for(int j=0;j<price.length+1;j++){
                if(j==0 || i==0)
                    arr[i][j] = 0;
                else if(j>=i){
                    arr[i][j] = Math.max(arr[i-1][j], price[i-1]+arr[i][j-i]);
                }else{
                    arr[i][j] = arr[i-1][j];
                }
            }
        }
        return arr[n-1][price.length];
    }

时间复杂性

O(n^2)