動态規劃

四、基本思想：動态規劃思想通常用于求解具有某種最優性質的問題。在這類問題中，可能會有許多可行解。其基本思想也是将待求解問題分解成若幹個子問題，先求解子問題，然後從這些子問題的解得到原問題的解。但是适合于用動态規劃求解的問題，經分解得到子問題往往不是互相獨立的。如果我們能夠儲存已解決的子問題的答案，而在需要時再找出已求得的答案，這樣就可以避免大量的重複計算。我們可以用一個表來記錄所有已解的子問題的答案。不管該子問題以後是否被用到，隻要它被計算過，就将其結果填入表中。

五、解題思路：

1.找出最優解的性質，刻畫其結構特征和最優子結構特征；

2.遞歸地定義最優值，刻畫原問題解與子問題解間的關系，找到狀态方程；

3.以自底向上的方式計算出各個子問題最優解，并避免子問題的重複計算；

4.根據計算最優值時得到的資訊，構造最優解。

---------------------

作者：銳小6

通過把原問題分解為相對簡單的子問題的方式求解複雜問題的方法。動态規劃常常适用于有重疊子問題和最優子結構性質的問題。

若要解一個給定問題，我們需要解其不同部分（即子問題），再合并子問題的解以得出原問題的解。 通常許多子問題非常相似，為此動态規劃法試圖僅僅解決每個子問題一次，進而減少計算量： 一旦某個給定子問題的解已經算出，則将其記憶化存儲，以便下次需要同一個子問題解之時直接查表。 這種做法在重複子問題的數目關于輸入的規模呈指數增長時特别有用。

共同點：二者都要求原問題具有最優子結構性質,都是将原問題分而治之,分解成若幹個規模較小(小到很容易解決的程式)的子問題.然後将子問題的解合并,形成原問題的解.

不同點：分治法将分解後的子問題看成互相獨立的，通過用遞歸來做。

　　　　 動态規劃将分解後的子問題了解為互相間有聯系,有重疊部分，需要記憶，通常用疊代來做。

最優子結構：當問題的最優解包含了其子問題的最優解時，稱該問題具有最優子結構性質。

重疊子問題：在用遞歸算法自頂向下解問題時，每次産生的子問題并不總是新問題，有些子問題被反複計算多次。動态規劃算法正是利用了這種子問題的重疊性質，對每一個子問題隻解一次，而後将其解儲存在一個表格中，在以後盡可能多地利用這些子問題的解。

描述最優解的結構

遞歸定義最優解的值

按自底向上的方式計算最優解的值

由計算出的結果構造一個最優解

注意需要需要二維數組用容器，c++動态配置設定二維數組太坑爹

有n件物品和一個容量為v的背包。第i件物品的費用是c[i]，價值是w[i]。求解将哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。 

f[i][v]表示前i件物品恰放入一個容量為v的背包可以獲得的最大價值。則其狀态轉移方程便是：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}。

------------------越是喧嚣的世界，越需要甯靜的思考------------------

合抱之木，生于毫末；九層之台，起于壘土；千裡之行，始于足下。

積土成山，風雨興焉；積水成淵，蛟龍生焉；積善成德，而神明自得，聖心備焉。故不積跬步，無以至千裡；不積小流，無以成江海。骐骥一躍，不能十步；驽馬十駕，功在不舍。锲而舍之，朽木不折；锲而不舍，金石可镂。蚓無爪牙之利，筋骨之強，上食埃土，下飲黃泉，用心一也。蟹六跪而二螯，非蛇鳝之穴無可寄托者，用心躁也。