相信學過編程的人都聽說過動態規劃。初學者都認為動態規劃很難，其實動態規劃并不難，只是有的時候很復雜而已。今天就跟大家淺談動態規劃吧。

動態規劃(dynamic PRogramming)是運籌學的一個分支，是求解決策過程(decision process)最優化的數學方法。20世紀50年代初美國數學家R.E.Bellman等人在研究多階段決策過程(multistep decision process)的優化問題時，提出了著名的最優化原理(principle of optimality)，把多階段過程轉化為一系列單階段問題，逐個求解，創立了解決這類過程優化問題的新方法——動態規劃。1957年出版了他的名著Dynamic Programming，這是該領域的第一本著作。

動態規劃問世以來，在經濟管理、生產調度、工程技術和最優控制等方面得到了廣泛的應用。例如最短路線、庫存管理、資源分配、設備更新、排序、裝載等問題，用動態規劃方法比用其它方法求解更為方便。                                           

動態規劃算法與其它算法相比，大大減少了計算量，豐富了計算結果，它沒有一個固定的解題模式，技巧性很強，是構造最優解的常用方法。             

多數編程教科書動態規劃一章里的第一個例子就是——

最長遞增子序列：輸入一個整數序列，求出其最長子序列的長度，使得子序列里前一項總比后一項小。（注：子序列的每一項都屬于原數列，且不一定連續）

舉個例子，假如輸入的數列為3 6 1 4 2 8 9 5 7，那么它的最長子序列一共有7個（3 6 8 9；3 4 8 9；3 4 5 7；1 4 8 9；1 4 5 7；1 2 8 9；1 2 5 7），最長子序列的長度是4。

那么我們該怎么編程解決呢？暴力而容易想到的方法是把每一個整數作為最長遞增子序列的最后一個整數然后進行深度優先搜索。然而如果你仔細思考，你會被這個方法的時間復雜度嚇住。設原序列的長度為n，那么就有O(n)個整數需要被搜索，每層搜索又會遞歸到O(n)個下一層搜索，而搜索又有O(n)層，也就是說數據如果坑，時間復雜度可能達到O(n^n)。要是n值有20，計算機就已經算的夠累了，更不說n=2000的情況了。這就到了動態規劃大顯神通的時候了。先說一句，使用動態規劃要注意空間和時間之間的轉化以及遞推的關系。

我們先看遞推的關系。每個新加的整數都會接上前面的一個序列或者自己組成一個新的序列。

然后就要擴大空間了。既然要求最長長度，那么就用一個數組記錄以當前數為最后一位的最長子序列長度。             

下面第一遍掃這n個數（掃到第i個數時需要把第1到i-1個數中小于第i個數的最大值找出，然后加1），

序列：3 6 1 4 2 8 9 5 7；

數組：1 2 1 2 2 3 4 3 4；

最后，將數組掃一遍，找出最大值。這個最大值就是最長子序列的長度。

你可以看到代碼量出奇的少。這是因為本題的遞推關系簡單，而且可以完全避免深度優先搜索。遇到難的動態規劃的題，其實只要找出遞推關系，用空間存儲合適的變量也能引刃而解。