126
技術社區[雲棲]
動態規劃法
1.定義及性質
動態規劃是一種在數學、計算機科學和經濟學中使用的，通過把原問題分解為相對簡單的子問題的方式求解複雜問題的方法。 動態規劃常常適用於有重疊子問題[1]和最優子結構性質的問題，用時往往遠少於樸素解法。
動態規劃背後的基本思想非常簡單。大致上，若要解一個給定問題，我們需要解其不同部分（即子問題），再合並子問題的解以得出原問題的解。 通常許多子問題非常相似，為此動態規劃法試圖僅僅解決每個子問題一次，從而減少計算量： 一旦某個給定子問題的解已經算出，則將其記憶化存儲，以便下次需要同一個子問題解之時直接查表。 這種做法在重複子問題的數目關於輸入的規模呈指數增長時特別有用。
2.算法設計步驟
動態規劃算法的設計可以分為4個步驟：
動態規劃法所處理的問題是一個多階段決策問題，一般由初始狀態開始，通過對中間階段決策的選擇，達到結束狀態。這些決策形成了一個決策序列，同時確定了完成整個過程的一條活動路線圖。動態規劃法一般需要經曆以下幾個步驟：
1.劃分階段：按照問題的時間或空間特征，把問題分為若幹個階段。在劃分階段時，注意劃分後的階段一定要是有序的或是可排序的，否則問題就無法求解。
2.確定狀態和狀態變量：將問題發展到各個階段時所處於的各種客觀情況用不同的狀態表示出來。當然，狀態的選擇要滿足無後效性。
3.確定決策並寫出狀態轉移方程：因為決策和狀態轉移有著天然的聯係，狀態轉移就是根據上一階段的狀態和決策來本階段的狀態。所以如果確定了決策，狀態轉移方程也就可以寫出。但事實上嚐嚐是反過來做，根據相鄰連個狀態之間的關係來確定決策方法和狀態轉移方程。
4.尋找邊界條件：給出的狀態轉移方程是一個遞推式，需要一個地推的終止條件或邊界條件。
實際應用中一般按一下步驟進行設計：
1.描述最優解的結構，可以利用子問題的最優解來構造原問題的最優解；
2.遞歸定義最優解的值
3.按自底向上的方式計算最優解的值
4.由計算出的結果構造一個最優解
3.動態規劃法的適用情況：
能采用動態規劃求解的問題的一般要具有3個性質：
(1) 最優化原理：如果問題的最優解所包含的子問題的解也是最優的，就稱該問題具有最優子結構，即滿足最優化原理。
(2) 無後效性：即某階段狀態一旦確定，就不受這個狀態以後決策的影響。也就是說，某狀態以後的過程不會影響以前的狀態，隻與當前狀態有關。
（3）有重疊子問題：即子問題之間是不獨立的，一個子問題在下一階段決策中可能被多次使用到。（該性質並不是動態規劃適用的必要條件，但是如果沒有這條性質，動態規劃算法同其他算法相比就不具備優勢）
4.算法實現說明
動態規劃的主要難點在於理論上的設計，也就是上麵4個步驟的確定，一旦設計完成，實現部分就會非常簡單。
使用動態規劃求解問題，最重要的就是確定動態規劃三要素：
（1）問題的階段 （2）每個階段的狀態
（3）從前一個階段轉化到後一個階段之間的遞推關係。
遞推關係必須是從次小的問題開始到較大的問題之間的轉化，從這個角度來說，動態規劃往往可以用遞歸程序來實現，不過因為遞推可以充分利用前麵保存的子問題的解來減少重複計算，所以對於大規模問題來說，有遞歸不可比擬的優勢，這也是動態規劃算法的核心之處。
確定了動態規劃的這三要素，整個求解過程就可以用一個最優決策表來描述，最優決策表是一個二維表，其中行表示決策的階段，列表示問題狀態，表格需要填寫的數據一般對應此問題的在某個階段某個狀態下的最優值（如最短路徑，最長公共子序列，最大價值等），填表的過程就是根據遞推關係，從1行1列開始，以行或者列優先的順序，依次填寫表格，最後根據整個表格的數據通過簡單的取舍或者運算求得問題的最優解。
f(n,m)=max{f(n-1,m), f(n-1,m-w[n])+P(n,m)}
動態規劃法的應用非常多，各大公司的筆試麵試題也經常出現，如數組中的最長遞增子序列問題、數組分割問題、數組的子數組之和的最大值問題。在後麵的文章中會羅列動態規劃法相關的麵試題來逐個突破。加油！
最後更新：2017-04-03 20:51:32