動态規劃一直被認為是最難了解的一種算法思想，什麼重疊子問題、動态轉移方程、最優子結構等等，一聽就高深莫測，沒有往下學習下去的動力
廢話不多說，我們直接先上一個經典的例子。那就是耳熟能詳的斐波那契數列問題。我們先來看一下問題的定義。
斐波那契數列的定義如下： 斐波那契數列指的是這樣一個數列 0,1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,..... 它以遞歸的方法來定義： f(0)=0，f(1)=1, f(n)=f(n-1)+f(n-2)（n>=2，n∈n*）
遞歸解決：
這個例子最直覺的方法就是用遞歸的方式來實作，畢竟斐波那契數列是用遞歸來定義的。我們來看一下代碼實作。
c#實作
這樣是不是很簡單。我們接下來看一下調用的遞歸樹。我們以fibs(6)為例。
其中每個結點表示要計算的斐波那契數列的第幾項，我們可以從上圖發現，會出現許多重複計算的問題，比如fib(4)就計算了兩次。這樣就會帶來時間和空間上的消耗，那我們有什麼方式可以避免重複計算的問題。我們可以使用遞歸中的“備忘錄”功能來解決。我們來看一下代碼如何實作。
我們把整個求解過程分為n個階段，每個階段去求解數列對應項的值。我們在解決目前問題時，也就是求解該對應項的值的時候，會依賴過去的狀态，也就是前面幾項的值來計算。比如我們在求解fibs(6)的時候，我們需要用到fibs(5)和fibs(4)這兩項。 我們來定義一個數組，來記錄每項的狀态。我們也叫做狀态轉移矩陣。 按照斐波那契數列的定義：
我們可以看到f(n)的值隻與他的前兩個狀态有關。是以我們隻要知道他的前兩個狀态，就可以求出f(n)。
初始化值f(0)=0，f(1)=1，我們直接放入數組中。
要想計算f(2)，我們需要知道f(0)和f(1)，因為上一步已經放入數組中，我們直接拿來用就好了，然後把f(2)的結果放入數組中。
要想計算f(3)，我們需要知道f(2)和f(1)，因為f(2)和f(1)已經存在數組裡了，我們直接拿來用就好了，然後把f(3)的結果放入數組中。
....
依此類推，知道計算到n為止。整個狀态轉移矩陣就計算好了。如下圖所示。我們以求解f(5)為例。
下面我們直接看代碼實作，這樣比較簡單明了。
上面的代碼是不是很簡潔明了。這就是一種用動态規劃來解決問題的思路。我們把問題分解為n個階段，一個階段一個階段去求解。然後通過目前狀态，來求出下一個狀态，動态的往前推進，這是不是還挺形象的