# 322. Coin Change

{% embed url="https://leetcode.com/problems/coin-change/" %}

## brute force

recursive like a tree, then do **BFS**, find the level which can subtract to 0 (11 -1 - 5 - 5 = 0

time: O(n^k), k is coins type



## DFS + memo (top down)

T: O(kn)

S: O(n)

```java
class Solution {
    public int coinChange(int[] coins, int amount) {
        return dfs(coins, amount, new Integer[amount+1]);
    }
    private int dfs(int[] coins, int amount, Integer[] memo) {
        if (amount == 0) { // no more amount, should return 0
            return 0;
        }
        if (amount < 0) {
            return -1;
        }
        if (memo[amount] != null) {
            return memo[amount];
        }
        int result = Integer.MAX_VALUE;
        for (int coin : coins) {
            int numbers = dfs(coins, amount - coin, memo);
            if (numbers == -1) {
                continue;
            }
            result = Math.min(result, 1 + numbers);
        }
        return memo[amount] = (result == Integer.MAX_VALUE ? -1 : result);
    }
}
```



```java
class Solution {
    public int coinChange(int[] coins, int amount) {
        return dp(coins, amount, new Integer[amount+1]);
    }
    private int dp(int[] coins, int amount, Integer[] memo) {
        if (amount == 0) {
            return 0;
        }
        if (amount < 0) {
            return -1;
        }
        if (memo[amount] != null) {
            return memo[amount];
        }
        int result = Integer.MAX_VALUE;
        for (int coin : coins) {
            int sub = dp(coins, amount - coin, memo);
            if (sub == -1) { // key point!
                continue;
            }
            result = Math.min(result, sub + 1);
        }
        return memo[amount] = (result != Integer.MAX_VALUE ? result: -1);
    }
    
}

// thought -> 
/*
fewest number of coins
subproblem -> f(10), f(9), f(6) , these are all dependent
f(11) = f(10) + 1 (if choose 1)
f(11) = f(9) + 1 (if choose 2)
f(11) = f(6) + 1 (if choose 5)

   f(11)
   /    
   f(10)  9.  6
   / \\    /
   9 8 5  8
   
k : how many kind of coins type
k^n , n subproblems
*/

// use memo -> k^n to k*n

   
   
```

## DP (bottom up

有幾種硬幣, 組成 amount => 是不是很像爬樓梯問題

#### subproblem & dp array:&#x20;

f(n) = min ( **f(n-k) )**,   for k in \[1,2,3]) + 1&#x20;

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MesV-NZOE3M6KHcRK-D%2F-MesWmtGZ8ageGXczz5q%2Fimage.png?alt=media\&token=7c490e4b-7b2a-4fb7-9859-b2669565645c)



time: O(kn), n: amount, k: coins' number, O(n)

space: O(n), n: amount

```java
class Solution {
    public int coinChange(int[] coins, int amount) {
        int dp[] = new int[amount+1]; // 初始結果都是amount+1
        Arrays.fill(dp, amount+1);
        dp[0] = 0;
        for (int i = 0; i < amount+1; i++) {
            for (int j = 0; j < coins.length; j++) {
                if (i - coins[j] >= 0) {
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return (dp[amount] > amount) ? -1 : dp[amount]; 
        // 初始amount+1,所以如果比 amount 大, 代表沒找到
    }
}
```



當前填滿容量 dp\[i] 最少需要的硬幣 =&#x20;

min(**之前填滿容量** dp\[i] **最少需要的硬幣 ,**    **填滿容量 dp\[i - coin 需要的硬幣 + 1個當前硬幣]** .  ）

for loop 去變換 coin 需要的硬幣,  f(n) = min ( **f(n-k) )**,   for k in \[1,2,3]) + 1&#x20;

因為是多個 f(n-k) 要找最小, &#x20;

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MesV-NZOE3M6KHcRK-D%2F-MesXaKPuff8hcl7GbUW%2Fimage.png?alt=media\&token=bcd5f247-e260-465e-aea9-ce722d5ff7ea)

所以在 dp\[i] 取得值, 要 **Math.min(dp\[i]**, dp\[i-coins\[j]+1)

**Math.min(dp\[i] . => 代表之前** **Math.min(dp\[i]**, dp\[i-coins\[j]+1)    => dp\[i-coins\[j]+1**算出的結果**&#x20;

```java
        for (int i = 0; i < amount+1; i++) {
            for (int j = 0; j < coins.length; j++) {
                if (i - coins[j] >= 0) {
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
```



### new version

```java
class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount+1];
        Arrays.fill(dp, amount + 1);
        
        dp[0] = 0;
        
        for (int i = 0; i < dp.length; i++) {
            for (int coin : coins) {
                if (i - coin >= 0) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        return dp[amount] != amount + 1 ? dp[amount] : -1;
    }
}
```
