Coin Change 2

You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin.

Example 1:

Input: amount = 5, coins = [1, 2, 5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

Example 2:

Input: amount = 3, coins = [2]
Output: 0
Explanation: the amount of 3 cannot be made up just with coins of 2.

Example 3:

Input: amount = 10, coins = [10] 
Output: 1

Note:

You can assume that

• 0 <= amount <= 5000
• 1 <= coin <= 5000
• the number of coins is less than 500
• the answer is guaranteed to fit into signed 32-bit integer

 class Solution {
       public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] += dp[i-coin];
            }
        }
        return dp[amount];
    }
}

Try it on Leetcode

Here, we are going to solve the problem using 1D array. The reason behind keeping dp[0] = 1 is that in problem note itself they mentioned coins will start from 1(i.e., minimum coin value is 1). [If we keep it as 0, then dp[0-1(minimum coin value)] will become dp[-1]. But if we use it as 1, then dp[1-1] = dp[0]]

Program Flow with each steps:

 dp[0] = 1, amount = 5

Iteration 1:
coin = 1
Inner Loop Iteration
dp[1] = dp[1] + dp[1-1] = dp[1] + dp[0] = 1
dp[2] = dp[2] + dp[2-1] = dp[2] + dp[1] = 1
dp[3] = dp[3] + dp[3-1] = dp[3] + dp[2] = 1
dp[4] = dp[4] + dp[4-1] = dp[4] + dp[3] = 1
dp[5] = dp[5] + dp[5-1] = dp[5] + dp[4] = 1

Iteration 2:
coin = 2
Inner Loop Iteration
dp[2] = dp[2] + dp[2-2] = dp[2] + dp[0] = 1 + 1 = 2
dp[3] = dp[3] + dp[3-2] = dp[3] + dp[1] = 1 + 1 = 2
dp[4] = dp[4] + dp[4-2] = dp[4] + dp[2] = 1 + 2 = 3
dp[5] = dp[5] + dp[5-2] = dp[5] + dp[3] = 1 + 2 = 3

Iteration 3:
coin = 5
Inner Loop Iteration
dp[5] = dp[5] + dp[5-5] = dp[5] + dp[0] = 3 + 1 = 4

Finally, dp[amount] = dp[5] = 4, which is the answer.

Submission Details

Related Posts:

Click here for May month challenges with solution and explanation
Click here for April month challenges with solution and explanation

Click here for June Month challenges with solution and explanation

The above solution can be formed only by optimizing our own different type of approach.

Subscribe us to receive updates instantly.

Please let us know about your views in comment section.

Happy Coding...😍