# 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;
}
}``````

Last updated