Coin Change : 找到重现给定金额的多种方法
Coin Change : Find number of ways to reproduce a given sum
Given a value N, if we want to make change for N cents, and we have infinite supply of each of S = { S1, S2, .. , Sm} valued coins, how many ways can we make the change? The order of coins doesn’t matter.
For example, for N = 4 and S = {1,2,3}, there are four solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}. So output should be 4. For N = 10 and S = {2, 5, 3, 6}, there are five solutions: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} and {5,5}. So the output should be 5.
问题的Link是:https://www.geeksforgeeks.org/coin-change-dp-7/
我确实遇到了所有的解决方案。
我已经使用 Matrix 方法为此提出了解决方案:
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <climits>
#include <map>
#include <set>
#include <queue>
#include <unordered_map>
#define ll long long
//Author: Nilargha Roy (neel13)
using namespace std;
int coinchangeways(int arr[],int n,int sum)
{
int dp[n+1][sum+1];
memset(dp,-1,sizeof(dp));
for(int j=1;j<n;j++)
{
dp[0][j]=0;
}
for(int i=0;i<n;i++)
{
dp[i][0]=1;
}
for(int i=1;i<n+1;i++)
{
for(int j=1;j<sum+1;j++)
{
if(arr[i-1] <= j)
dp[i][j]=dp[i][j-arr[i-1]] + dp[i-1][j];
else
dp[i][j]=dp[i-1][j];
}
}
return dp[n][sum];
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
#ifdef __APPLE__
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
int n;
cin>>n;
int arr[n];
for(int i=0;i<n;i++)
cin>>arr[i];
int sum; cin>>sum;
cout<<coinchangeways(arr,n,sum);
}
但是,当我将数组 = {1,2,3} 和 SUM = 5 作为输入时,输出应该是:5 而我得到的是 1。任何人都可以指出其中的逻辑错误我的代码?
当你 运行 你的函数在所有 for 循环之后。您将获得如下所示的 DP。
1 0 0 -1 -1 -1
1 1 1 0 -1 -2
1 1 2 1 1 -1
-1 1 2 0 2 1
dp[3][5] = 1 这就是你得到 1 的原因。
使用一维数组的版本:
int coinchangeways(int arr[], int n, int sum)
{
int dp[sum+1];
memset(dp, 0, sizeof(dp));
dp[0] = 1;
for (int i = 0; i < n; i++)
{
for (int j = arr[i]; j <= sum; j++)
{
dp[j] += dp[j - arr[i]];
}
}
return dp[sum];
}
Given a value N, if we want to make change for N cents, and we have infinite supply of each of S = { S1, S2, .. , Sm} valued coins, how many ways can we make the change? The order of coins doesn’t matter. For example, for N = 4 and S = {1,2,3}, there are four solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}. So output should be 4. For N = 10 and S = {2, 5, 3, 6}, there are five solutions: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} and {5,5}. So the output should be 5.
问题的Link是:https://www.geeksforgeeks.org/coin-change-dp-7/
我确实遇到了所有的解决方案。
我已经使用 Matrix 方法为此提出了解决方案:
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <climits>
#include <map>
#include <set>
#include <queue>
#include <unordered_map>
#define ll long long
//Author: Nilargha Roy (neel13)
using namespace std;
int coinchangeways(int arr[],int n,int sum)
{
int dp[n+1][sum+1];
memset(dp,-1,sizeof(dp));
for(int j=1;j<n;j++)
{
dp[0][j]=0;
}
for(int i=0;i<n;i++)
{
dp[i][0]=1;
}
for(int i=1;i<n+1;i++)
{
for(int j=1;j<sum+1;j++)
{
if(arr[i-1] <= j)
dp[i][j]=dp[i][j-arr[i-1]] + dp[i-1][j];
else
dp[i][j]=dp[i-1][j];
}
}
return dp[n][sum];
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
#ifdef __APPLE__
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
int n;
cin>>n;
int arr[n];
for(int i=0;i<n;i++)
cin>>arr[i];
int sum; cin>>sum;
cout<<coinchangeways(arr,n,sum);
}
但是,当我将数组 = {1,2,3} 和 SUM = 5 作为输入时,输出应该是:5 而我得到的是 1。任何人都可以指出其中的逻辑错误我的代码?
当你 运行 你的函数在所有 for 循环之后。您将获得如下所示的 DP。
1 0 0 -1 -1 -1
1 1 1 0 -1 -2
1 1 2 1 1 -1
-1 1 2 0 2 1
dp[3][5] = 1 这就是你得到 1 的原因。
使用一维数组的版本:
int coinchangeways(int arr[], int n, int sum)
{
int dp[sum+1];
memset(dp, 0, sizeof(dp));
dp[0] = 1;
for (int i = 0; i < n; i++)
{
for (int j = arr[i]; j <= sum; j++)
{
dp[j] += dp[j - arr[i]];
}
}
return dp[sum];
}