# Leetcode 322. Coin Change

## 題解

### 動態規劃

#### Top down

import math

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        n = len(coins)
        memo = [0 for i in range(amount)]
        def bfs(rem: int):
            if rem < 0: return -1
            if rem == 0: return 0
            if memo[rem-1] != 0: return memo[rem-1]
            mini = (10 ** 4) + 1
            for coin in coins:
                res = bfs(rem - coin)
                if res >= 0 and res < mini:
                    mini = res + 1
            memo[rem-1] = -1 if mini == (10 ** 4) + 1 else mini
            return memo[rem-1]
        if amount == 0: return 0
        bfs(amount)
        return memo[amount-1]

#### Bottom up (不是最優)

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        # Time complexity: O(n)
        # Space complexity: O(n)
        # Bottom up
        # SOS:
        # f(n) = min(f(n-ci)) + 1
        # f(0) = 0
        # n < 0 => f(n) = -1
        if amount == 0: return 0 # edge case
        int_max = (10 ** 4) + 1
        memo = [0 for i in range(amount)]
        def f(n: int):
            if n < 0: return -1
            if n == 0: return 0
            if memo[n-1]: return memo[n-1]
            mini = int_max
            for coin in coins:
                res = f(n-coin)
                if res >= 0 and res < mini:
                    mini = res + 1
            memo[n-1] = mini
            return memo[n-1]
        for i in range(1, amount+1):
            f(i)
        return -1 if memo[amount-1] == int_max else memo[amount-1]