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

Basic CS Algorithm Review

• Quick Sort
• 直覺想法：
  divide and conquer
• divide:
  一個陣列輸入，透過pivot來分三類：
• 小於（丟進子問題排序）
• pivot
• 大於（丟進子問題排序）
• conquer:
  把上述三類合再一起
• return:
  當子問題輸入的陣列長度小於等於1 (不用再排序了，所以回傳)
• 平均複雜度：Ｏ(nlogn)
  每個點走一次和pivot比較大小 -> n
  binary divide and conquer -> logn (樹的深度）
• code：