我不明白我哪里做错了,因为每当我运行代码时,输出是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;
}
你有一个错误。价格数组p
按长度索引,最小长度为1
,但数组中的第一个价格位于索引0处。你的代码永远不会访问p[0]
。
最简单的修复方法是在价格数组的开头添加一个虚拟值。
int p[] = { 0, 1, 5, 8, 9, 10, 17, 17, 20 };
修改后,代码按预期打印22
。