-1

我正在尝试使用动态编程方法解决硬币找零问题。我所做的是使用了占用空间较小的一个。这是我的代码：

 #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

4

2 回答 2

0

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

于 2015-07-15T15:55:32.087 回答
0

因为您将值返回为“int”数据类型，这导致“有符号整数溢出：1656720088 + 569919779 无法以 int 类型表示”错误。

尝试更改函数的返回数据类型和用于将结果存储为“uint64_t”的 DP 表的数据类型。

进行以下更改；1.更改将结果存储为“uint64_t”的数组的数据类型。2.将函数的返回数据类型更改为“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.将接收特定函数返回值的变量的数据类型更改为“uint64_t”。

uint64_t res = ways(n, coins);
于 2020-08-16T17:35:10.513 回答