# 322. Coin Change

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

应该最典型的dp了。

> We note that this problem has an optimal substructure property, which is the key piece in solving any Dynamic Programming problems. In other words, the optimal solution can be constructed from optimal solutions of its subproblems.

状态转换方程——凑`n`需要的最少硬币数，等于凑`n-t`需要的最小硬币数加1，`t`是`coins`内小于`n`的任意面值：

$$
f(n) = f(n-t) + 1 \quad for ; t; in;<coins>;if;n>=t
$$

### 01/07/2021 update:

更新 bottom-up 的解法，个人觉得更直观、好理解一点，也容易写得简短。

{% tabs %}
{% tab title="top-down" %}

```python
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        if not amount: return 0
        dp = {n:1 for n in coins}
        threshold = min(coins)
        
        def fewestCoins(n):
            if n < threshold: return float('inf')
            if n in dp: return dp[n]
            else:     
                dp[n] = min([fewestCoins(n-c) for c in coins if c < n]) + 1
                return dp[n]
        
        res = fewestCoins(amount)
        return res if res <= amount else -1
```

{% endtab %}

{% tab title="bottom-up" %}

```python
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [0 for _ in range(amount+1)]
        
        for n in range(1, amount+1):
            prev = [x for x in [dp[n-c] for c in coins if n >= c] if x >= 0]
            dp[n] = min(prev) + 1 if prev else -1
        
        return dp[-1]
```

{% endtab %}
{% endtabs %}
