518. Coin Change 2

Question

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

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

Solutions

  • Method 1: Recursion TLE 
      class Solution {
      private int amount;
      private int[] coins;
      private int res;
      public int change(int amount, int[] coins) {
          this.amount = amount;
          this.coins = coins;
          dfs(0, 0);
          return res;
      }
      private void dfs(int index, int sum){
          if(sum == amount) res++;
          else if(sum < amount){
              for(int i = index; i < coins.length; i++){
                  dfs(i, sum + coins[i]);
              }
          }
      }
  }
  • Method 2: dp 
      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 = 1; i <= amount; i++){
                  if(i - coin >= 0)
                      dp[i] += dp[i - coin];
              }
          }
          return dp[amount];
      }
  }