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