動態規劃 1 ——基本概念

首先申明下面要寫的總結主要摘自在網上找到的一篇動態規劃總結教程（沒找到作者），內容基本相同。寫這些東西純屬自己動態規劃復慣用。知乎上大神很多，其中有不妥的不對的地方歡迎指出，大家共同進步！！！

1 動態規劃要素

動態規劃有三要素：階段、狀態和決策。

階段：

把一個問題的過程，恰當地分為若干個相互聯繫的階段，以便於按一定的次序去求解。描述階段的變數稱為階段變數。階段的劃分，一般是根據時間和空間的自然特徵來進行的，但要便於問題轉化為多階段決策。

狀態：

表示每個階段開始所處的自然狀況或客觀條件。通常一個階段有若干個狀態（也可能只有一個狀態），描述過程狀態的變數稱為狀態變數。

決策：

表示當過程處於某一階段的某個狀態時，可以作出不同的決定，從而確定下一階段的狀態，這種決定稱為決策。

一般流程：

劃分階段 -> 正確選擇狀態變數 -> 確定狀態轉移方程

-> 確定階段指標函數和最優指標函數，建立動態規劃基本方程。

2 動態規劃的適用範圍

動態規劃用於解決多階段決策最優化問題，但也不是所有最優化問題都可以用動態規劃來解答。用動態規劃的最優化問題要滿足兩個條件：

a) 最優子結構(最優化原理)

作為整個過程的最優策略具有這樣的性質：無論過去的狀態和決策如何，相對於前面的決策所形成的狀態而言，餘下的決策序列必然構成最優子策略。」也就是說，一個最優策略的子策略也是最優的。

b) 無後效性

如果某階段狀態給定後，則在這個階段以後過程的發展不受這個階段以前各段狀態的影響。就是說在狀態i求解時用到狀態j，狀態j求解用到狀態k...,狀態N。而狀態N要用到狀態i，這樣的求解過程形成了環就沒法用動態規劃解答。也就是說當前狀態是前面狀態的完美總結，現在與過去無關。有的問題換一個劃分狀態或階段的方法就滿足無後效性，這樣的問題仍然可以用動態規劃解。

如果狀態變數不能滿足無後效性的要求，應適當地改變狀態的定義或規定方法。

3 動態規劃解決問題的一般思路

拿到多階段決策最優化問題後，第一步要判斷這個問題是否可以用動態規劃解決，如果不能就要考慮搜索或者貪心了。當確定問題可以用動態規劃後，可以用下面介紹的方法解決問題：

a) 模型匹配法

這個是最先考慮的。主要是看看問題是不是自己熟悉的某個基本的模型，如背包模型等，是的話就直接套用了，當然要注意其中的變動。有很多考題是基本模型的變型，小心條件。這些基本的模型將在下面的分類中以演算法題的形式一一介紹。

b) 三要素法

仔細分析問題嘗試著確定動態規劃的三要素，不同的問題的確定方形不同：

先確定階段的問題：數塔問題和走路問題。

先確定狀態的問題：大多數都是先確定狀態。

先確定決策問題：背包問題。

一般都是先從比較明顯的地方入手，至於怎麼知道哪個明顯就看經驗，多做題就會發現。

c) 尋找規律法

耐心分析幾組數據，找找有沒有什麼規律。

d) 邊界條件法

找到問題的邊界條件，然後考慮邊界條件與它鄰接狀態之間的關係。

接下來幾篇通過具體例題來說明。

【說明】接下來幾篇中的例題的代碼結構基本都是一個Solution類，類裡面的solve函數是解題演算法部分。