# 切割棒以获得最大利润

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


      +---+---+---+---+---+---+---+---+---+
(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 |   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+---+


     +---+---+---+---+---+---+---+---+---+
(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 |   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+---+


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];


       +---+---+---+---+---+---+---+---+---+
(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|
+---+---+---+---+---+---+---+---+---+


## 用 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)