518.Coin-Change-2

518. Coin Change 2

题目地址

https://leetcode.com/problems/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

代码

Approach #1 Dynamic Porgramming 1D

dp[i] 表示组成钱数i的不同方法

Complexity Analysis

• Time complexity: O(N×amount), where N is a length of coins array.

• Space complexity: O(amount) to keep dp array.

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 + 1; i++) {
        dp[i] += dp[i - coin];
      }
    }

    return dp[amount];
  }
}

Approach #2 Dynamic Programming 2D

dp[i][j] 代表只用前i个硬币(coin)来组成j钱数(amount)

public int change(int amount, int[] coins) {
      int[][] dp = new int[coins.length+1][amount+1];
      dp[0][0] = 1;

      for (int i = 1; i <= coins.length; i++) {
          dp[i][0] = 1;
          for (int j = 1; j <= amount; j++) {
              dp[i][j] = dp[i-1][j] + (j >= coins[i-1] ? dp[i][j-coins[i-1]] : 0);
          }
      }
      return dp[coins.length][amount];
  }

Approach #3 DFS

class Solution {
    public int change(int amount, int[] coins) {
        // order coins in order to prune recursion
        Arrays.sort(coins);
        // init memorization to -1 (unvisited)
        int[][] memo = new int[amount + 1][coins.length];
        for (int[] arr: memo) {
            Arrays.fill(arr, -1);
        }

        return dfs(coins, amount, 0, memo);
    }

     private int dfs(int[] coins, int amount, int index, int[][] memo) {
        if (amount == 0) return 1;
        if (index == coins.length) return 0;
        if (memo[amount][index] != -1) return memo[amount][index];

        int cnt = 0;
        for (int i = index; i < coins.length; i++) {
            if (coins[i] > amount) break;
            // using this coin as many times as possible before going to next coin
            int count = 1;
            while (count * coins[i] <= amount) {
                cnt += dfs(coins, amount - count * coins[i], i + 1, memo);
                count++;
            }
        }

        // memorize
        memo[amount][index] = cnt;
        return cnt;
    }
}