---
# System prepended metadata

title: Classic Recursion/DP
tags: [Week 9, Recursion, DP]

---

# Classic Recursion/DP
###### tags:`Recursion` `DP` `Week 9`

## 湊零錢
- Greedy (not the best solution)
- Example:
    - input: n=8, S={1,4,6}
    - output: f(n,S)= *the minimum post stamp to get n dollars*
```
Recursive Solution
f(n,S)=
{
    1, if n E S
    inf, if n<min(S)
    1+min(f(n-x,S)), else
}
```
### Recursive Solution:
```python=
n=8
S={1,4,6}
def f(m,S):
    if m in S: return 1
    if m < mins(S): return n+1
    return 1+min({f(m-x,S) for x in S})
```
### DP Solution:
```python=
n=8
S={1,4,6}
a = [n+1]*(n+1)
for x in range(min(S),n+1):
    if x in S: 
        a[x] = 1
        continue
    I = {x-s for s in S if x>s}
    a[x] = 1 + min({a[i] for i in I})
print(f'n = {n}, S = {S} \
    => f(n,S) = {a[n] if a[n] <= n else "inf"}')

```

## 貼郵票