为什么我在硬币找零动态编程方法中遇到错误的测试用例？

Question

我正在尝试使用动态规划方法解决硬币找零问题。我所做的是使用较少 space 消耗的一个。这是我的代码：

 #include <cmath>
 #include <cstdio>
 #include <vector>
 #include <iostream>
 #include <algorithm>
 #include <cstring>
 using namespace std;
 int coinchange(int S[],int m,int n){
 long long table[n+1];

 // Initialize all table values as 0
memset(table, 0, sizeof(table));

// Base case (If given value is 0)
table[0] = 1;

// Pick all coins one by one and update the table[] values
// after the index greater than or equal to the value of the
// picked coin
for(int i=0; i<m; i++)
    for(int j=S[i]; j<=n; j++)
        table[j] += table[j-S[i]];

return table[n];
}

int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */   
int nn,mm,ar[250];
cin>>mm>>nn;
for(int i=0;i<nn;i++)
    cin>>ar[i];
long long c=coinchange(ar,nn,mm);
cout<<c;
return 0;
}

它显示了以下测试用例的错误答案：输入： 250 24 41 34 46 9 37 32 42 21 7 13 1 24 3 43 2 23 8 45 19 30 29 18 35 11 预期输出： 15685693751

Answer 1

代码正确。您只是从 coinchange 函数返回 'int' 而不是 'long long'。其他一切都是正确的。尝试通过打印中间值来调试您的代码。它可以帮助您更好地理解您的代码以备将来使用。

Answer 2

因为你 return 值是“int”数据类型，导致“有符号整数溢出：1656720088 + 569919779 不能用 int 类型表示”错误。

尝试将函数的 return 数据类型和您用来存储结果的 DP table 的数据类型更改为“uint64_t”。

进行以下更改； 1.Change 将结果存储为“uint64_t”的数组的数据类型。 2.Change 函数的 return 数据类型为“uint64_t”。

uint64_t ways(int n, vector<int> coins) {
    
    uint64_t t[n+1];
for(int i=0;i<=n;i++)
    t[i]=0;
t[0]=1.0;
for(int i=0;i<coins.size();i++)
{
    for(int j=coins[i];j<=n;j++)
    {
       // if(j>=coins[i])
        t[j]+=t[j-coins[i]];
    }
}
return t[n];
}

2.Change 从特定函数接收 returned 值的变量的数据类型，如“uint64_t”。

uint64_t res = ways(n, coins);

为什么我在硬币找零动态编程方法中遇到错误的测试用例？

Why am i getting a test case wrong in coin change dynamic programming approach?

arrays

dynamic-programming

coin-change