基本思想

動態規劃是針對一類求最優解的問題的算法， 其核心是將一個問題分解成為若干個子問題（這里對應下文的子問題使用條件）， 部分類似于分治的思想（不懂得可以參考歸并排序）， 通過求每一次的最優決策， 來得到一個最優解。在這里最重要的就是子問題的思想。

另一種理解方式數是DP的核心是加法原理（下文的人人為我形遞歸）和乘法原理（下文的我為人人形遞歸）， 通過這兩個原理， 在當狀態的前有限多個狀態中找到最優解來求得當前狀態， 而對于前一個或者前幾個狀態采用同樣的方法知道求出邊界狀態，這種方法最惡心的就是邊界狀態

在學會搜索之后， 最簡單入門DP的方法就是記憶話搜索， 但是后來會發現大多數DP題目因為時間和內存的限制并不能使用遞歸（函數的遞歸調用會占用棧內存， 另外函數的遞歸調用也將占用大量的時間）

子問題解決法的適用條件

需同時滿足一下三點：

1.具有相同的子問題：我們必須保證我們分割成的子問題也能按照相同的方法分割成更小的自問題， 并這些自問題的最終分割情況是可以解決的。

2.滿足最優子結構：就是一個決策的子決策也是最優的

3.無后效性：這是DP中最重要的一點， 他要求每個子問題的決策不能對后面其他未解決的問題產影響， 如果產生就無法保證決策的最優性， 這就是無后效性。往往需要我們找到一個合適的狀態。
··這條非常重要
··這條非常重要
··這條非常重要
舉個例子：我們在LIS中先求前M項的LIS， 然后依次向后求， 直到str.len， 這就是因為我們在求前M項的過程中， 對(M + 1)→(str.len)并無影響。消除后效性的例子等等會單開一片博客來講。

常用的解題步驟

前兩天剛剛被大牛虐過DP， 姑妄言之：

第一步：確定子問題。 在這一步重點是分析那些變量是隨著問題規模的變小而變小的， 那些變量與問題的規模無關。
第二步：確定狀態：根據上面找到的子問題來給你分割的子問題限定狀態
第三步：推到出狀態轉移方程：這里要注意你的狀態轉移方程是不是滿足所有的條件， 注意不要遺漏。
第四步：確定邊界條件：先根據題目的限制條件來確定題目中給出的邊界條件是否能直接推導出， 如果不行也可以嘗試從邊界條件反推（舉個例子：a(n)→a(2)有遞推關系， 但是a(2)→a(1)不符合上述遞推關系， 我們就可以考慮用a(1)來倒推出a(2)， 然后將遞推的終點設置為a(2)）;
第五步：確定實現方式：這個依照個人習慣 就像是01背包的兩層for循環的順序
第六步：確定優化方法：很多時候你會發現走到這里步的時候你需要返回第1步重來。首先考慮降維問題（優化內存）， 優先隊列、四邊形不等式（優化時間）等等。

常用方法

以下是方法， 但是不要局限在這里， 方法是無限的

（1）模型匹配法：熟練記憶并且理解LIS、LCS、01背包、完全背包、區間模型、樹狀模型。基本就是將原模型加以變化后加以套用

（2）三要素法：
·······先確定階段：如數塔問題， 先確定當前選的是第幾層。
·······先確定狀態：這是最常用的絕大多數的DP都是這么做的。
·······先確定決策：背包問題（選還是不選第i種物品）
這是個經驗問題， 然而我還沒有這種經驗。

（3）尋找規律法：從小的狀態開始推， 耐心找規律， 或者可以在本地暴力打表， 暴力出奇跡， 不打2、3頁那都不叫打表，幾年省賽徹底領悟了，不想說啥。

（4）邊界條件法： 一般邊界時容易導出狀態關系的地方

（5）增加約束條件法：這條就對應著上文的消除后效性，以后的博客會有例題

總結

以上是生活随笔為你收集整理的动态规划(1)：基本思路以及步骤的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。