Dynamic Programming

Dynamic Programming

• DP 
• Careful Brute Force
• Sub-problems + memorization + Reuse + guessing
• Must be DAG (Directed Acyclic Graph)

Fibonacci Example

假設想求取F(n)，過程中F(n-3) 會重算兩次

→直覺的想法就是算了第一次以後存起來，以後可以直接用，不用在往下算。

• Recursive想法：
• T(n) = T(n-1) + T(n-2) +T(1)
  >= 2(T(n-2))
• Time = O(2^(n/2)) exponential time cost
• DP想法：
• 只需要把F(1),F(2),...,F(n)每個都呼叫一次，且每次只需要O(1) constant（把兩個子問題相加）
• Time = O(n) linear time cost
• Bottom-Up (實際運作時可以省下很多function call，因為沒有recursive只有loop）

REF:

Dynamic Programming I: Fibonacci, Shortest Paths