medium Coin Change II

Problem Statement

Given an integer array coins, where coins[i] = x represents the coin of amount x, and integer amount, return the total number of distinct ways to make a amount of money using a given set of coin denominations. If that amount of money cannot be made up by any combination of the coins, return 0.

You can have an infinite number of each coin.

Examples

• Example 1:

  • Input: amount = 4, coins = [1,2,3]
  • Expected Output: 4
  • Justification: The four ways to make 4 are: [1,1,1,1], [1,1,2], [2,2], and [1,3].

• Example 2:

  • Input: amount = 10, coins = [2, 5, 3, 6]
  • Expected Output: 5
  • Justification: The five ways to make 10 are: [2,2,2,2,2],[2,2,3,3], [5,5], [2,2,6], and [2,3,5]`.

• Example 3:

  • Input: amount = 0, coins = [7,3]
  • Expected Output: 1
  • Justification: There is only one way to make 0, which is by not using any coins at all.

Solution

To solve this problem, we'll use dynamic programming because it allows us to break down the problem into smaller, manageable subproblems, each of which can be solved just once and then stored for future reference. This approach is effective because it eliminates the need for redundant calculations, thus optimizing performance.

We'll create a table (array) where each entry represents the number of ways to make up an amount using the available denominations up to that point. Starting with the base case where the amount is 0 (which has 1 way, using no coins), we progressively calculate the number of ways for all amounts up to the target, including it.

Our strategy ensures efficiency and scalability, capable of handling a wide range of inputs. It is designed to systematically explore all combinations of coin usage, dynamically building upon the solutions of smaller amounts to reach the final target. This methodology not only guarantees that all possible combinations are considered but also leverages previously computed results for rapid computation of subsequent solutions.

Step-by-Step Algorithm

1. Initialization: Create an array dp of length amount + 1 and initialize all its elements to 0. This array will hold the number of ways to make each amount from 0 to amount. Set dp[0] = 1 because there is exactly one way to make an amount of 0, which is by using no coins.

2. Iterate Over Coins: Loop through each coin in the coins array. For each coin, proceed to the next step.

3. Update DP Array: For the current coin, iterate over the dp array starting from the index equal to the coin's value up to amount. For each index i, update dp[i] by adding the value of dp[i - coin] to it. This step effectively adds the number of ways to make the amount i by including the current coin to the number of ways i could be made without it.

4. Repeat: Repeat the above step for each coin in the coins array.

5. Result: After iterating through all coins, dp[amount] will contain the total number of ways to make the target amount using the given coins.

Algorithm Walkthrough

Given amount = 10 and coins = [2, 5, 3, 6], let's walk through the algorithm step-by-step:

Initial Setup

• amount = 10
• coins = [2, 5, 3, 6]
• Initial dp array: [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

Processing Coin 2:

1. Update for amount = 2:

   • dp[2] += dp[2 - 2]
   • dp array becomes [1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0]

2. Update for amount = 3:

   • dp[3] += dp[3 - 2]
   • dp array remains the same.

3. Update for amount = 4:

   • dp[4] += dp[4 - 2]
   • dp array becomes [1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0]

4. Update for amount = 5:

   • dp[5] += dp[5 - 2]
   • dp array remains the same.

5. Update for amount = 6:

   • dp[6] += dp[6 - 2]
   • dp array becomes [1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0]

6. Update for amount = 7:

   • dp[7] += dp[7 - 2]
   • dp array remains the same.

7. Update for amount = 8:

   • dp[8] += dp[8 - 2]
   • dp array becomes [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0]

8. Update for amount = 9:

   • dp[9] += dp[9 - 2]
   • dp array remains the same.

9. Update for amount = 10:

   • dp[10] += dp[10 - 2]
   • dp array becomes [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1]

Processing Coin 5:

1. Update for amount = 5:

   • dp[5] += dp[5 - 5]
   • dp array becomes [1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1]

2. Update for amount = 6:

   • dp[6] += dp[6 - 5]
   • dp array remains the same.

3. Update for amount = 7:

   • dp[7] += dp[7 - 5]
   • dp array becomes [1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1]

4. Update for amount = 8:

   • dp[8] += dp[8 - 5]
   • dp array becomes [1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1]

5. Update for amount = 9:

   • dp[9] += dp[9 - 5]
   • dp array becomes [1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1]

6. Update for amount = 10:

   • dp[10] += dp[10 - 5]
   • dp array becomes [1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 2]

Processing Coin 3:

1. Update for amount = 3:

   • dp[3] += dp[3 - 3]
   • dp array becomes [1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 2]

2. Update for amount = 4:

   • dp[4] += dp[4 - 3]
   • dp array becomes [1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 2]

3. Update for amount = 5:

   • dp[5] += dp[5 - 3]
   • dp array becomes [1, 0, 1, 1, 1, 2, 1, 1, 1, 1, 2]

4. Update for amount = 6:

   • dp[6] += dp[6 - 3]
   • dp array becomes [1, 0, 1, 1, 1, 2, 2, 1, 1, 1, 2]

5. Update for amount = 7:

   • dp[7] += dp[7 - 3]
   • dp array becomes [1, 0, 1, 1, 1, 2, 2, 2, 1, 1, 2]

6. Update for amount = 8:

   • dp[8] += dp[8 - 3]
   • dp array becomes [1, 0, 1, 1, 1, 2, 2, 2, 3, 1, 2]

7. Update for amount = 9:

   • dp[9] += dp[9 - 3]
   • dp array becomes [1, 0, 1, 1, 1, 2, 2, 2, 3, 3,2]

8. Update for amount = 10:

   • dp[10] += dp[10 - 3]
   • dp array remains [1, 0, 1, 1, 1, 2, 2, 2, 3, 3, 4]

Processing Coin 6:

1. Update for amount = 6:

   • dp[6] += dp[6 - 6]
   • dp array becomes [1, 0, 1, 1, 1, 2, 3, 2, 3, 3, 4]

2. Update for amount = 7:

   • dp[7] += dp[7 - 6]
   • dp array becomes [1, 0, 1, 1, 1, 2, 3, 2, 3, 3, 4]

3. Update for amount = 8:

   • dp[8] += dp[8 - 6]
   • dp array becomes [1, 0, 1, 1, 1, 2, 3, 2, 4, 3, 4]

4. Update for amount = 9:

   • dp[9] += dp[9 - 6]
   • dp array becomes [1, 0, 1, 1, 1, 2, 3, 2, 4, 4, 4]

5. Update for amount = 10:

   • dp[10] += dp[10 - 6]
   • dp array becomes [1, 0, 1, 1, 1, 2, 3, 2, 4, 4, 5]

Return value of dp[amount], which is 5.

Code

public class Solution {

  public int change(int amount, int[] coins) {
    // dp[i] will be storing the number of solutions for value i.
    // We need amount+1 rows as the table is constructed in bottom-up manner using the base case (dp[0] = 1)
    // Initialize all dp values as 0.
    int[] dp = new int[amount + 1];

    // Base case (If given value is 0)
    dp[0] = 1;

    // Pick all coins one by one and update the dp[] values after the index greater
    // than or equal to the value of the picked coin
    for (int coin : coins) {
      for (int j = coin; j <= amount; j++) {
        dp[j] += dp[j - coin];
      }
    }

    return dp[amount];
  }

  public static void main(String[] args) {
    Solution solution = new Solution();

    // Example 1
    System.out.println(solution.change(4, new int[] { 1, 2, 3 })); // Expected Output: 4

    // Example 2
    System.out.println(solution.change(10, new int[] { 2, 5, 3, 6 })); // Expected Output: 35

    // Example 3
    System.out.println(solution.change(0, new int[] { 7, 3 })); // Expected Output: 1
  }
}

Complexity Analysis

Time Complexity

• : Here, m is the amount and n is the number of coin denominations. The time complexity arises because we iterate over each coin denomination and for each coin, we iterate over all amounts from the coin's value up to m.

Space Complexity

• : The space complexity is linear with respect to the amount m because we maintain a dynamic programming table (dp array) of size m + 1 to store the number of ways to make each amount up to m.