Comment on page

# 518.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;
}
}