# 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:

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:

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"}')

## 貼郵票