Problem in Coin Change DP

help
1

I’m trying to solve the coin-change DP problem. I’m making DP array with a bottom approach with the recurrence relation as dp[i]+=dp[i-S[j]] where S is the array of coins available and is of size m. The following is my code what I observed is my recurrence relation is not mutually exclusive since its adding some recurrences again.

long long int count( int S[], int m, int n )
    {
        int dp[n+1]={0};
        dp[0]=1;
        for(int i=1; i<=n; i++){
            for(int j=0; j<m; j++){
                if(i-S[j]<0) continue;
                dp[i] += dp[i-S[j]];
            }
        }
        return dp[n];
        //code here.
    }
2 
long long int count( int S[], int m, int n )
    {
        int dp[n+1]={0};
        dp[0]=1;
        for(int i=1; i < n ; i++){
            for(int j = S[i]; j<=m; j++){
                dp[j] += dp[j-S[i]];
            }
        }
        return dp[n];
    }
  • I have made necessary changes to your code.
3

That’s not right, dp[0] is equal to 1 in this type of implementation. I see nothing wrong with this implementation though.