這是數據結構與算法的第二節內容，在講這節之前，我單獨拿出來一個講解一個很重的算法，下一節，我會拿LeetCode上面的動態規劃題來看，先看動態規劃
有關動態規劃（Dynamic Programming）算法的題目很多。動態規劃（Dynamic Programming）算法也算一個比較考驗邏輯能力的算法了；
動態規劃算法的核心
理解一個算法就要理解一個算法的核心，動態規劃算法的核心是什麼呢？看下面
最重要的一句話，記住求解的過程，就是找一個數據結構，記下你每一步求解的答案；
動態規劃算法的兩種形式
上面已經知道動態規劃算法的核心是記住已經求過的解，記住求解的方式有兩種：①自頂向下的備忘錄法 ②自底向上。
為了說明動態規劃的這兩種方法，舉一個最簡單的例子：求斐波拉契數列Fibonacci 。先看一下這個問題，下面就是這個數列的計算方法：
Fibonacci (n) = 1; n = 0
Fibonacci (n) = 1; n = 1
Fibonacci (n) = Fibonacci(n-1) + Fibonacci(n-2)
這道題，給你一個n？讓你求Fibonacci (n)？怎麼求，最笨的方法是什麼呢？直接來個遞歸是不是？
看遞歸，這裡用java寫了（注意語言只是工具）
這個遞歸你要是看不懂，真得好好補補。是不是邏輯很簡單；我們既然研究算法，題是做出來了，但是這樣子好嗎？
先看看下這個遞歸的執行流程
.....
看出什麼來了嗎？我們在求f（6）的過程中，遞歸了2次f（4），5次f（2）.....
如果數字夠大比如1000000000，那麼空間和時間上開銷，只能呵呵；
有沒有什麼辦法改進呢？當然有動態規劃，我說了動態規劃最主要的是記錄每一步的求解過程，之後我們換個名詞叫子問題，就是子問題的解，來看看（是不是腦海中已經快有答案了？子問題不就是前面f（4），f（2）...的值嗎?）
①自頂向下的備忘錄法
這種方法還是用遞歸，只不過在遞歸的過程中，我們把每一個求解完的f（n）給存下來了，比如在求解f（6）的時候，我們先得去求解f（5）和f（4），我再去遞歸，求f（5），這次我們需要求f（4）和f（3），之後我們先不管，我再往下是不是一定會求出f（4）？我們記錄下來這個f（4），等我們回去求解f（6）產生的子問題f（4）的時候，是不是就不用再往下遞歸，直接用就可以？（好好理解，很簡單，因為複雜的再後面）
所以這個時候我們需要一個數據結構記錄我們的每一步計算的值？選什麼數據結構呢？大家想一下，我們要的這個數據結構只要方便我們查就行？比如我想馬上知道f（4）等於多少，不用循環，更不用遍歷，最好一下就能找到，毫無疑問最簡單的就是數組；
一起看看代碼
②自底向上的動態規劃
自頂向下還是利用了遞歸，上面算法不管怎樣，計算fib（6）的時候最後還是要計算出fib（1），fib（2），fib（3）……,那麼何不先計算出fib（1），fib（2），fib（3）……,呢？這也就是動態規劃的核心，先計算子問題，再由子問題計算父問題。記住這幾句話，收益匪淺，先解決局部問題，在向著大問題發展；來看看代碼
現在動態規劃的兩種方法都介紹完了，我們來比較下，這兩種方法，自頂向下，我們是從大問題先入手，在求解過程中，遇到每個子問題就記錄它的值，可以說是被動的；自底向上的過程，就是我們刻意用動態規劃，直接從子問題入手，最後求解大問題；
好了，今天就到這裡，看來還需要一篇文章，來說動態規劃了，下篇文章，如果大家有學習算法和數據結構這方面的興趣，就關注下，方便大家閱讀，和跟上節奏；謝謝大家（文/村裡的霸王）
關鍵字: 數據結構 規劃 Programming
