自上而下动态规划的棒材切割

Question

我不明白我哪里做错了，因为每当我运行代码时，输出是35，但当我在非自顶向下运行它时，它是22(这是我在Geeks4Geeks https://www.geeksforgeeks.org/cutting-a-rod-dp-13/中看到的正确输出)

我哪里做错了?

#include <iostream>
#include <cstring>
#include <limits.h>
using namespace std;
int arr[1000];
int Cut_Rod(int p[], int n);
int main() {
int p[] = { 1, 5, 8, 9, 10, 17, 17, 20 };
int n = sizeof(p)/sizeof(p[0]) - 1;
memset(arr, -1, sizeof(arr)); // set all values inside arr as -1
int maxValue = Cut_Rod(p, n);
cout << "Max profit: " << maxValue << endl;
return 0;
}
int Cut_Rod(int p[], int n) {
int q;
if (arr[n] >= 0)
return arr[n];
if (n == 0)
q = 0;
else {
q = INT_MIN;
for (int i = 1; i <= n; i++) {
q = max(q, p[i] + Cut_Rod(p, n - i));
}
}
arr[n] = q;
return q;
}

Answer 1

你有一个错误。价格数组p按长度索引，最小长度为1，但数组中的第一个价格位于索引0处。你的代码永远不会访问p[0]。

最简单的修复方法是在价格数组的开头添加一个虚拟值。

int p[] = { 0, 1, 5, 8, 9, 10, 17, 17, 20 };

修改后，代码按预期打印22。