Can anyone explain this ogic how it comes problem statement and solution given

#1

solution: https://github.com/BlakeBrown/HackerRank-Solutions/blob/master/Algorithms/Dynamic%20Programming/The%20Coin%20Change%20Problem.cpp

#2

@rssrivastavarohan
This is a standard DP problem. At each instance during your traversal , you have two choices - whether to include the current coin in your total or not. You are supposed to entertain both the possibilities and return the sum of those results. The solution code that you have shared uses the bottom up DP approach. I am sharing its equivalent top down DP approach as I personally find it easier to understand.

ll dp[1000][1000]; // all elements initialised to -1

// s is the array of denominations
// amount is the total amount that needs to be made
// n is the size of array s
// i is the current index

ll money(int *s,int n,ll amount,int i){
    if(amount == 0){
        //If amount is 0 , there is 1 way to make this amount by using no coins
        return 1;
    }
    if(i == n){
        //No more coins left , no way to make the amound
        return 0;
    }
    if(amount < 0){
        //Amount is -ve , no way to make this amount using given coins
        return 0;
    }

    if(dp[i][amount]!=-1){
        return dp[i][amount];
    }

    ll ans = 0 ;
    ll includeCurrentCoin = money(s,n,amount-s[i],i);
    ll excludeCurrentCoin = money(s,n,amount,i+1) ;

    ans = includeCurrentCoin + excludeCurrentCoin ; 

    dp[i][amount] = ans;

    return ans;
}
#3

Hi Tarun could you please try me to understood in that solution how they have landed on for(int i = 0; i < M; i++) {
for(int j = coin[i]; j <= N; j++) {
change[j] += change[j-coin[i]];
}
}

Please help Tarun

#4

Tarun are you there?

#5

@rssrivastavarohan
The way to go about such dp problems as you would have seen in your video tutorials is to look how the dp table gets filled.
The statement
change[j] += change[j-coin[i]];
in bottom up approach is equivalent to the statement
ll includeCurrentCoin = money(s,n,amount-s[i],i);
in top down approach.
The idea behind this statement is simple that at each instance we try to include the current coin that we have and subtract its value from our total amount. The no of ways that would make up our current amount is equal to the summation of all such possibilities where we try it with all the given coins.