坐井觀天

https://www.youtube.com/watch?v=oBt53YbR9Kk

動態規劃，簡稱DP，算是一個我覺得蠻powerful的思維

首先要先建立recursive的觀念，並且做樹狀展開，再來將已經計算過的結果存起來做取用

1. 簡化問題: 把問題簡化成小的問題，並且recursive解決

2. 圖形化成tree: recursive解法可以圖形化成tree, 每個tree的subtree為題目簡化出來的小問題

3. LUT: 簡化出來的subtree是否可以存取結果進入LUT，此時只要是LUT裡面可以找到的解答，subtree就不願繼續往下長樹

範例當然是大家的好朋友Fibonacci數列

0 1 1 2 3 5 8 13 ...

1. 將問題簡化: Fib[n] = Fib[n-1] + Fib[n-2] when n > 1; Fib[0] = 0; Fib[1] = 1

2. 圖形化成tree: 

                       Fib[30]

                 Fib[29]

              Fib[28]

            ...

Fibonocci而言是一個只有一個child的tree

3. LUT

將Fib[0], Fib[1]存入LUT, Fib[n], n>2每次recursion都使用LUT裡面找到Fib[n-1], Fib[n-2]

Leetcode上面可以看到沒有使用DP的結果

runtime 20 ms, memory 5.7MB

使用DP之後速度明顯提升

runtime 0ms, memory 6MB