We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
dp[j] stores the number of solutions for j. For base case j=0, number of solutions is 1(not using any coin). Now in the for loop, i represents the number of coins you are using. Initially i=0, so you cannot create change for any j>0, hence dp[j]=0 for j>0. Now in each iteration you add a new coin and update the number of solutions for those j which have value not less than the value of ith coin. This update is just adding the number of solutions when we use the ith coin which is equal to the number of solutions of creating change for j-coins[i]. We are finally done when we use all the coins and so we print dp[n].
The Coin Change Problem
You are viewing a single comment's thread. Return to all comments →
dp[j] stores the number of solutions for j. For base case j=0, number of solutions is 1(not using any coin). Now in the for loop, i represents the number of coins you are using. Initially i=0, so you cannot create change for any j>0, hence dp[j]=0 for j>0. Now in each iteration you add a new coin and update the number of solutions for those j which have value not less than the value of ith coin. This update is just adding the number of solutions when we use the ith coin which is equal to the number of solutions of creating change for j-coins[i]. We are finally done when we use all the coins and so we print dp[n].