如何解决最大数量限制的杆切割问题允许削减多少？

我知道如何使用动态规划解决杆切割问题。 但是，当我们限制允许的最大切割次数时，动态规划无法给出正确的答案。即使我也无法想到该问题的递归解决方案。帮助。

问题是这样的，
确定通过切割杆并出售碎片可获得的最大收入。
给定长度为 N 的杆，以及长度为 i 的杆的价格表 P(i)。您可以在给定的杆上进行不超过 K 次切割。

example:
N=10
K=3
| p(1) = 1 | p(1) = 1 p(2) = 5 | p(2) = 5 p(3) = 8 | p(3) = 8 p(4) = 9 |p(5) = 10| p(6) = 22 | p(6) = 22 p(7) = 17 | p(7) = 17 p(8) = 20 | p(8) = 20 p(9) = 24 | p(9) = 24 p(10) = 30 | p(10) = 30 |

通过将杆切成长度为 6 和 4 的 2 段（总切割次数 = 1，小于 K = 3），可获得的最大收入为 31。

我们可以通过添加第二维（即迄今为止的切割次数）来扩展动态规划解决方案。

D[n][k]，一根长度的杆的最大收入n准确地使用k割，可以定义如下：

D[n][k] = max(price[i] + D[n-i-1][k-1]) for all i in {1, 2, ..., n}

既然我们想要at most K削减，不exactly，最大收益为：

maxRevenue(N) = max(D[N][k]) for all k in {1, 2, ..., k}

这会是O(N²K)，因为我们需要循环所有k（相比O(N²)对于经典问题）。

（Java）代码：

int[] price = {1, 5, 8, 9, 10, 22, 17, 20, 24, 30};
int N = price.length;
int K = 3;
int[][] D = new int[N+1][K+1];

for (int n = 1; n <= N; n++)
    D[n][0] = price[n-1];

for (int k = 1; k <= K; k++)
for (int n = 0; n <= N; n++)
for (int i = 0; i <= n-1; i++)
    D[n][k] = Math.max(D[n][k], price[i] + D[n-i-1][k-1]);

int best = 0;
for (int k = 0; k <= K; k++)
    best = Math.max(best, D[N][k]);

System.out.println(best);

现场演示 http://ideone.com/7WTEDI.