動态規劃算法

dynamic programming 基本介紹

dynamic programming是五大常用算法政策之一，簡稱dp，譯作中文是“動态規劃”，可就是這個聽起來高大上的翻譯坑苦了無數人，因為看完這個算法你可能會覺得和動态規劃根本沒太大關系，它對“動态”和“規劃”都沒有太深的展現。

舉個最簡單的例子去先淺顯的了解它，有個大概的雛形，找一個數組中的最大元素，如果隻有一個元素，那就是它，再往數組裡面加元素，遞推關系就是，當你知道目前最大的元素，隻需要拿目前最大元素和新加入的進行比較，較大的就是數組中最大的，這就是典型的dp政策，将小問題的解儲存起來，解決大問題的時候就可以直接使用。

fibonacci 斐波拉契數列動态規劃實作

第一個數是1，第二個數也是1，從第三個數開始，後面每個數都等于前兩個數之和。要求：輸入一個n，輸出第n個斐波那契數。

還是我們上節讨論遞歸與分治政策時候舉的第一個例子——fibonacci數列問題，它實在太經典了，是以将其反複拿出來說。

我們如果深入分析一下上節說過的遞歸方法解決fibonacci數列，就會發現出現了很多重複運算，比如你在計算f(5)的時候，你要計算f(4)和f(3),計算f(4)又要計算(3)和f(2),計算f(3)，又要計算f(2)和f(1),看下面這個圖

對f(3)和f(2)進行了重複運算，這還是因為5比較小，如果要計算f(100),那你可能要等到天荒地老它還沒執行完

上面就是遞歸的解法，代碼看着很簡單易懂，但是算法複雜度已經達到了o(2^n),指數級别的複雜度，再加上如果n較大會造成更大的棧記憶體開銷，是以非常低效。

我們知道導緻這個算法低效的根本原因就是遞歸棧記憶體開銷大，對越小的數要重複計算的次數越多，那既然我們已經将較小的數，諸如f(2),f(3)……這些計算過了，為什麼還要重複計算呢，這時就用到了dp政策，将計算過的f(n)儲存起來。我們看看代碼：

arr數組初始化為0，arr[i]就表示f(i),每次先判斷arr[i]是否為0，如果為0則表示未計算過，則遞歸計算，如果不為0，則表示已經計算過，那就直接傳回。

這樣的好處避免了很大程度上重複的計算，但是對棧記憶體的開銷雖然有減小但還不是很顯著，因為隻要有遞歸，棧記憶體就免不了有較大開銷。是以針對fibonacci數列我們還有一個遞推的方式來計算，其實這也符合dp政策的思想，都是将計算過的值儲存起來。

動态規劃解題步驟

1、确定狀态

簡單的說，就是解動态規劃時需要開一個數組，數組的每個元素f[i]或者f[i][j]代表什麼，類似解數學題中，xyz代表什麼一樣，具體分為下面兩個步驟：

-------研究最優政策的最後一步

-------化為子問題

2、轉移方程

根據子問題定義直接得到

3、初始條件和邊界情況

初始條件一般都是a[0]、a[1]這種，多看看

邊界條件主要是看數組的邊界，數組越不越界

4、計算順序

利用之前的計算結果