演算法 — 動態規劃(DP)-1
使用的程式語言為C++
今天想要跟大家介紹的是，演算法中的一個基本方法，動態規劃（Dynamic Programming, 簡稱DP）
這邊要請大家記住，動態規劃的重點就是「用表格做紀錄」，表格也就是代表陣列，把已經算過的東西，放在表格裡面，避免之後不斷做重算的動作（筆者我一開始也不太能理解這句話的意思，直到看到下面的例子）。
費氏數列(Fibonacci)，相信有在接觸程式的各位對這個數列，一定都還挺熟悉的，再學習遞迴的過程中，一定會提到這個數列，這邊就不多提此數列在數學中的含義等等。
規則如下：
我們可以看到上面，初始值 fib(0) = 0, fib(1) = 1，之後每一個數字都是前面兩個數字相加後的和
例如：fib(3) = fib(1) + fib(2) = 1 + 1 = 2
我們可以依照這個規則很快的寫出一個遞迴函式去做費氏數列的計算。
但是！！
如果用遞迴的寫法的話，當我們輸入量太多的話就出現錯誤，因為記憶體會不夠。
如果用這個程式碼輸入50的話，可能會出現這樣的錯誤。
那有什麼方法可以解決呢？
這時候就要試用到動態規劃，畫表格紀錄的方法，其實也就是建立「陣列」去儲存已經計算過的數字。
看到上面這個圖，可以看到，每次出現一個fib(2)時，我們就要再多做一次 fib(0) 跟 fib(1) 相加的動作，可是當我們有用一個陣列把他記住的話，每次出現fib(2)就可以直接套用，不用再走進去遞迴跑一次，這樣可以節省不少時間。
「以空間換取時間」也就是這個意思！
程式碼：
可能有人會有疑問為什麼要用long long 型態。因為如果用int的話，當輸入太大的話，會超出int原本的範圍，所以這邊要使用long long才不會因為值太大而出錯。（筆者自己測試100000也會是對的，再多可能就會要出錯了。）
希望大家有了解到動態規劃畫表格的精神～～
