動態規劃題目的特點

動態規劃的題目沒有固定的樣式，要解決動態規劃題目首先要知道哪些題目可以使用動態規劃求解，最基本的分類有以下三種，

1.計數題

這種題目往往要求給出符合某種條件的解的數量，類似的題目有：
---->有多少種方式走到右下角
---->有多少種方式選出k個數使得和為sum

2.求最大最小值

顧名思義，就是題目要求你給出一個最大值或最小值，不論是花費的最小值還是其他型別的最大最小值，都在這個范圍內，類似的題目有：
---->從左上角走到右下角路徑的最大數字和
---->最長上升子序列長度

3.求存在性

存在性題目一般要求回傳boolean型別的值，題目會問我們是否存在一個解符合條件，此類問題有：
---->取石子游戲，先手是否必勝
---->能不能選取k個數，使他們的和為sum

動態規劃解題模板

通常來說，動態規劃完整的解題思路包括四個組成部分：確定狀態、狀態轉移方程、初始條件和邊界條件、計算順序，
以下以一例解說：
題目：現有2元，5元，7元三種不同規格的硬幣，數量不限，從中選出k個硬幣，使得能組成n元，求k的最小值，（原題中硬幣的規格為傳入的一個陣列，此處取為[2,5,7]便于理解）

1.確定狀態

解開動態規劃需要設定一個陣列，確定每個元素代表什么意思，
確定狀態需要兩個意識：“最后一步”、“子問題”，

1.1最后一步：即為最優策略中的最后一步決策，

在例題中，我們可以很輕易地得到，最后一步即為最后一枚硬幣A_k，

1.2子問題：去掉最后一步之后，剩下待處理的問題與原問題相似，

去掉最后一步，剩下的子問題題為：選出k-1個硬幣，使得能組成n-A_k元，求k-1的最小值，
而這個子問題依然可以繼續劃分子問題，直到最后需要組成0元，.

2.狀態轉移方程

我們在第一步確定狀態中已經得到了“最后一步”與“子問題”，在第二步按照“最后一步”與“子問題”即可寫出動態轉移方程，

那么我們知道了最后一步與子問題之后，怎么寫出狀態轉移方程，我們要解決n元的組合問題，不妨設最小的硬幣數為f(n)，那么n在子問題中可以分解為0,1,2,…,n總共n個數，在寫代碼時可以設一個長度為n+1的陣列來保存，

以例題為例，我們知道了最后一步是最后一枚硬幣，但不知道到底是2元、5元還是7元，那么就應該列出所有情況:2元、5元和7元，

對應的子問題即為f(n-2)、f(n-5)和f(n-7)，

最后，我們再回到原問題上，因為要求最小值，那么得到
f(n) = min{f(n-2)+1,f(n-5)+1,f(n-7)+1}

這里為什么要加一，是因為對于原問題來說，子問題到原問題需要多加一枚硬幣，這很好理解，就是說，到子問題需要k枚硬幣的話，那么從這個子問題到原問題硬幣數必須加一，

為什么不用遞回：使用遞回時，不同的分支無法檢測其他分支中的運算，難免造成重復計算，當數值較大時，所消耗的時間空間會指數級上升，有時甚至會造成StackOverFlow（SOF），如下圖：

f(20)與f(18)都計算了多次，非常影響效率，

3.初始條件和邊界條件

3.1初始條件

初始條件是考慮剛開始時某些部分的初始值是否要設定以及設定為多少

我們首先可以知道要組成0元需要0枚硬幣，可以直接設 f(0) = 0;
其他的初始條件還有不能組成硬幣的1元，3元等，不需要過多設定，否則有些難以考慮到的值難免疏漏，可以把這一部分交給邊界條件實作，
而f(2) f(5) f(7)這些應該交給回圈來計算得出，沒有必要一定自己設定初始值，

3.2邊界條件

邊界條件考慮的是什么時候停止，

很顯然，當我們運算時難免得到n為負數的情況，那么我們在求最小值的問題中，應該將n為負數的情況設定為MAX_VALUE，

現在再看正數中不能實作數，比如f(1)
f(1) = min{f(-1)+1,f(-4)+1,f(-6)+1}
因為三個數都是負數，則可以得到全為無限大，那么f(1)可以直接得到值為無限大，（在程式中我們應該注意MAX_VALUE經過加一后溢位的事實，所以實際代碼應有針對性改進，除此之外還有陣列下標不能為負數）

4.計算順序

通常情況下動態規劃為從左到右從上到下（從上到下為二維陣列考慮，一般不出現三維才能求解的情況，至今還未遇到過），

當我們分析計算順序時，只需要考慮一個問題：計算f[n]時，呼叫的數值是否全都經過計算
如：f(n) = min{f(n-2)+1,f(n-5)+1,f(n-7)+1}，當計算f(n)時要保證其中所有的數都計算過，則應該從左往右遍歷

小結

該博客面向初學者，其中有不足之處還請指正，

在真實刷題程序中，還有一些特別的情況存在，比如：不必初始化、不必額外設定邊界條件（陣列遍歷結束即結束）、狀態轉移方程難以表示（因為本人沒有系統地學習此類相關的運算式格式，有一部分不會用狀態轉移方程表示，比如遍歷陣列內所有的值得到一個符合條件的值即回傳，這種運算式是真的不會寫，但是寫代碼能表示出來也是可以的），

對于演算法題中各類復雜的題目，還是需要融會貫通之后才有足夠的能力解出，不建議照著模板寫題，最好的方式還是學習時間和實踐代碼區分開來，有時間的可以去各大刷題網站寫一下簡單的動態規劃，看完這篇博客應該是簡單難度的題都能A了，

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/279900.html

標籤：其他

上一篇：JavaScript編程基礎練習題---干貨分享

下一篇：C語言實作簡單的三子棋