DP: Dynamic Programming
- DP ≈ "Careful Brute foree"
- DP ≈ "Subproblems + reuse"
1. Fibonacci numbers
F1 = F2 = 1
Fn = Fn - 1+ Fn-2
goal: Compute Fn
2. Naive recursive algarithrm
Fib(n):
if n <= 2: f=1
else: f = fib(n-1) + fib(n-2)
return f
T(n) = T(n-1) + T(n-2) + O(1)
3. Memoized DP algarithm:
memo = {}
fib(n):
if n in memo: return memo[n];
if n <= 2: f=1
else: f = fib(n-1) + fib(n-2)
memo[n] = f
return f
tree
4.Fib(k) only recureses the first time it`s called.
- memoized call O(1)
-
nonmemiozed call is n:
- fib(1) , fib(2) ,,,,,,,fib(n)
- nonerecursive work per call: O(1)
- time = O(n)
DP ≈ Recursion + memoization
- memoize(remember) & reuse sollutions
- to subproblems that help solve the problem
=> time = # subproblems * time/subproblem
don`t count resursions
Bottom-up DP algorithm
fib = {}
for k in range(1, n+1):
if k <= 2: f =1
else f=fib[k-1] + fib[k-2]
fib[k] = f
return fib[n]
- exactly same compatation
- topological sort of subproblem dependency(拓扑排序)
DAG:
Shortest Paths:
Guessing: don`t know
the answer? guess.....
try all guesses.
take best one
.....
s -> a -> c-> u->v
guess first edge
S(s, v) = S(s, u) + W(u,v)
Subproblem dependencies should be acyclic
