本蒟蒻最近忙于切題, 不會的題大多數(shù)來源于動態(tài)規(guī)劃, 雖然動態(tài)規(guī)劃的思想貌似挺簡單, 但是想出來比較難。

如何你不了解什么是動態(tài)規(guī)劃? 請移步<<算法導論>>第15章.

如何解決一個動態(tài)規(guī)劃問題呢? 我認為最重要的是找出問題的最優(yōu)子結構. 動態(tài)規(guī)劃的思想就是將一個問題分解為若干個子問題，再通過子問題的最優(yōu)解構造出問題的最優(yōu)解。

證明問題具有最優(yōu)子結構

最常用的方法是反證法, 我們來看看(0-1)背包問題是怎么證明的?

(0-1)背包問題可以歸納為在有限個可供選擇的方案中，尋找滿足一定約束的最好方案, 這實際上就是一個整數(shù)規(guī)劃問題

? ??

我們下面來證明這個問題具有最優(yōu)子結構, 也就是它的解包括子問題的最優(yōu)解

假設我們已經(jīng)找到了一組最優(yōu)解(y1,y2....yn),?我們先將問題的規(guī)模縮小一下, 那么我們可以推出(y2, y3 ... yn)是下面子問題的最優(yōu)解:

假設(z2, z3, ... , zn)是上面子問題的最優(yōu)解, 即(y2, y3,... yn)不是該子問題的最優(yōu)解, 這樣我們就假設了該問題不具有最優(yōu)子結構了.

繼續(xù)得出

說明(y1,z2,z3,?,zn)是比(y1,y2,y3,?,yn)更優(yōu)的一個解，與原假設(y1,y2,y3,?,yn)是問題的最優(yōu)解矛盾!

因此, 我們證明了該問題具有最優(yōu)子結構, 這個方法其實來自于<<算法導論>>里介紹的"剪貼法", 我們就可以通過子問題的最優(yōu)解來構造出原問題的最優(yōu)解惹!

例題

接下來我們來看一波題,

(洛谷P1280 尼克的任務)：?https://www.luogu.com.cn/problem/P1280

我們先來簡單地證明一下這個問題的最優(yōu)子結構, 為了提高體驗避免滿屏幕數(shù)學符號，這里用不太嚴謹?shù)姆绞阶C明。

和背包問題的證明方法一樣, 假設我們得到了該問題的一組最優(yōu)解, 也就是題目中所說的能獲得最大摸魚時間的任務組(y1, y2,...yn), 我們嘗試將問題規(guī)模縮小, 把工作時間縮小為n-1, 這個子問題的解為(y1, y2,...yn-1) (這里不太嚴謹, 因為如果最后一組工作的開始時間<=n-完成該工作的時間, 那么該問題的解還是(y1, y2, ... , yn))

我們還是老套路, 假設(z1, z2, ... , zn-1)是該子問題的最優(yōu)解, 則(y1, y2, ..., yn-1)不是該子問題的最優(yōu)解. 這樣我們可以推出選擇(z1, z2, ... , zn-1)時工作時間會更短, 于是(z1, z2, ... , zn)是該問題的最優(yōu)解, 而(y1, y2, ..., yn) 不是, 與假設產(chǎn)生矛盾! 于是這個問題的最優(yōu)子結構得證!

根據(jù)最優(yōu)子結構間的關系推出最優(yōu)解

證明了問題的最優(yōu)子結構, 只是解決這個問題的一小步, 我們還要找出各個子問題間的關系， 并利用這些子問題來構造出原問題的一個最優(yōu)解!

一般地, 我們用dp數(shù)組(dp table)來保存子問題的結果, 所以定義dp的含義以及如何優(yōu)化子問題的空間(是二維數(shù)組或是多維數(shù)組?)是十分重要的。

回到上題, 我們可以定義dp[i] : 在第i時刻的最大空閑時間。 通過觀察可得, 最后結果一定是通過dp[1], dp[2] ,...., dp[n]得到的!

在第i時刻, 有兩種情況(有任務和無任務)

這道題采用一種逆推的方法(即i 從 n 到 1枚舉)

有任務時, 設k為該任務的時長, 我們需要枚舉出該時刻開始的所有任務的時長k, 進行比較后選擇能獲得最大摸魚時間的那個就完事了， 狀態(tài)方程:?dp[i] = max(dp[i], dp[i + k])

無任務時, 此時的空閑時間為上一刻的空閑時間+1?: dp[i] = dp[i + 1] + 1

你可能會想是一刻dp[i+1]是多少? 那不是另一個子問題嗎??然后計算機又笨笨地判斷i+1有無任務，計算出最大空閑時間, 這樣貌似構成了遞歸?(實際上動態(tài)規(guī)劃是一種帶著"記憶"的遞歸)

接下來寫出代碼應該問題不大:

?