c++ - 动态规划 : Rod cutting implementation error

Question

给定一根长度为 n 英寸的杆和一张价格为 pi 的表格i = 1, 2, ... n, 求切分可获得的最大 yield rn杆和卖件。

Bottom_Up_Cut_Rod(p, n)
1 let r[0...n] be a new array
2 r[0] = 0
3 for j = 1 to n
4 q = -infinity
5 for i = 1 to j
6 q = max(q; p[i] + r[j - i])
7 r[j] = q
8 return r[n]

实现

#include <iostream>
#include <algorithm>

using namespace std;

int RodCut(long long P[],long long n)
{
    long long r[n];
    r[0]=0;
    for(long long j=0;j<n;j++)
    {
         long long q = -100000;
         for(long long i=0;i<j;i++)
         {
             q = max(q , P[i] + r[j-i]);
         }
         r[j] = q;
    }

    return r[n];
}

int main()
{
    long long num;
    long long N;
    long long K;

    cin>>N;

    long long a[N];
    for (long long i = 0; i < N; i++)
    {
        cin>>num;
        a[i] = num;
    }

    int res = 0;
    res = RodCut(a,N);

    cout<<"Answer : "<<res;

    return 0;
}

我的输入是 1 5 8 9 10 17 17 20 24 30，但输出是 2686348。我的代码有什么问题？

Answer 1

有几个问题。您希望主循环从 j = 1 到 n，因为它代表了您可以使用 j 个元素做的最好的事情。

您应该坚持使用 int 或 long long。

int r[n+1];
r[0]=0;

// Calculate best we can do with j elements
for(int j=1;j<=n;j++) {
    int q = -100000;
    for(int i=0;i<j;i++) {
        q = max(q , P[i] + r[j-i-1]);
    }
    r[j] = q;
}

return r[n];

这似乎为我提供了适用于各种输入的正确解决方案。