硬币兑换：找到许多方法来复制给定的金额

Question

给定一个值N，如果我们想换N美分，并且我们有无限量的S={S1，S2，…，Sm}值的硬币，我们可以用多少种方式来换？硬币的顺序无关紧要。例如，对于N=4和S={1,2,3}，有四种解决方案：{1,1,1}，{1,1,2}，{2,2}，{1,3}。所以输出应该是4。对于N=10和S={2,5,3,6}，有五个解：{2,2,2,2,2}，{2,2,3,3}，{2,2,6}，{2,3,5}和{5,5}。所以输出应该是5。

问题的联系是：https://www.geeksforgeeks.org/coin-change-dp-7/

我确实遇到了所有的解决方案。

我已经使用矩阵方法来解决这个问题：

#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作为输入时，当我得到1时，输出应该是：5。有人能指出我代码中的逻辑错误吗？

Answer 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。

Answer 2

使用1d数组的版本：

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];
}