4步套路，解決動態規劃問題

1、確定問題狀態

• 提煉最后一步
• 的問題轉化

2、轉移方程，把問題方程化
3、按照實際邏輯設置初始條件和邊界情況
4、確定計算順序并求解

結合實例感受下：

你有三種硬幣，分別面值2元，5元和7元，每種硬幣都有足夠多。買一本書需要27元。如何用最少的硬幣組合正好付清，不需要對方找錢？

關鍵詞“用最小的硬幣組合正好付清”——“最小的組合”，求最值問題，動態規劃。

**正常人第一反應思路:**最少硬幣組合?優先使用大面值硬幣——7+7+7+5=26 額？可求解目標是27啊……改算法——7+7+7+2+2+2=27，總共用了6枚硬幣正好27元.實際正確答案：7+5+5+5+5=27，才用了5枚硬幣。所以這里貪心算法是不正確的。

套路用起來：

第一步，確定問題狀態。

動態規劃問題求解需要先開一個數組，并確定數組的每個元素f[i]代表什么，就是確定這個問題的狀態。類似于解數學題中，設定X，Y，Z代表什么。

A、確定狀態首先提取【最后一步】

最優策略必定是K枚硬幣a1, a2,…, aK 面值加起來是27。

找出不影響最優策略的最后一個獨立角色，這道問題中，那枚最后的硬幣“aK”就是最后一步。把aK提取出來，硬幣aK之前的所有硬幣面值加總是27- aK因為總體求最硬幣數量最小策略，所以拼出27- aK 的硬幣數也一定最少（重要設定）。

B、**轉化子問題。**最后一步aK提出來之后，我們只要求出“最少用多少枚硬幣可以拼出27- aK”就可以了。

這種與原問題內核一致，但是規模變小的問題，叫做子問題。

為簡化定義，我們設狀態f(X)=最少用多少枚硬幣拼出總面值X。我們目前還不知道最后的硬幣aK面額多少，但它的面額一定只可能是2/5/7之一。如果aK是2，f(27)應該是f(27-2) + 1 (加上最后這一枚面值2的硬幣）如果aK是5，f(27)應該是f(27-5) + 1 (加上最后這一枚面值5的硬幣）如果aK是7，f(27)應該是f(27-7) + 1 (加上最后這一枚面值7的硬幣）除此以外，沒有其他的可能了。

至此，通過找到原問題最后一步，并將其轉化為子問題。為求面值總額27的最小的硬幣組合數的狀態就形成了，用以下函數表示：

f(27) = min{f(27-2)+1, f(27-5)+1, f(27-7)+1}

第二步，轉移方程，把問題方程化。

f[X] = min{f[X-2]+1, f[X-5]+1, f[X-7]+1}（動態規劃都是要開數組，所以這里改用方括號表示）

實際面試中求解動態規劃類問題，正確列出轉移方程正確基本上就解決一半了。

但是請問：這與遞歸有什么不同？？

遞歸的解法：

// f(X)返回最少用多少枚硬幣拼出Xint f(int X) {// 0元錢只要0枚硬幣if (X == 0) return 0;// 初始化用無窮大（為什么是正無窮？）int res = MAX_VALUE;// 最后一枚硬幣是2元if (X >= 2) {res = Math.min(f(X – 2) + 1, res);}// 最后一枚硬幣是5元if (X >= 5) {res = Math.min(f(X – 5) + 1, res);}// 最后一枚硬幣是7元if (X >= 7) {res = Math.min(f(X – 7) + 1, res);}return res;}

執行圖如下：

要算f(27)，就要遞歸f(25)、f(22)、f(20)，然后下邊依次遞歸……（三角形表示）。

問題明顯——重復遞歸太多。

這是求f(27)，還可以勉強遞歸。如果求f(100)呢？簡直是天文數字。最終結果就是遞歸超市。

求總體最值，一定優先考慮動態規劃不要憨憨的去遞歸。

插入一下~

需要掌握的動態規劃面試解題技巧還包括坐標型、位操型、序列型、博弈型、背包型、雙序列以及一些高難面試題解。

本文篇幅有限無法逐一講清，大家來白嫖我的在線分享吧（純干貨）。

第三步，按照實際邏輯設置邊界情況和初始條件。

**【必做】**否則即使轉移方程正確也大概率無法跑通代碼。

f[X] = min{f[X-2]+1, f[X-5]+1, f[X-7]+1}的邊界情況是[x-2]/[x-5]/[x-7]不能小于0（硬幣面值為正），也不能高于27。

故對邊界情況設定如下：

如果硬幣面值不能組合出Y，就定義f[Y]=正無窮例如f[-1]=f[-2]=…=正無窮；f[1] =min{f[-1]+1, f[-4]+1,f[-6]+1}=正無窮,

**特殊情況：**本題的F[0]對應的情況為F[-2]、F[-5]、F[-7]，按照上文的邊界情況設定結果是正無窮。

但是實際上F[0]的結果是存在的（即使用0個硬幣的情況下），F[0]=0。可是按照我們剛剛的設定，F[0]=F[0-2]+1= F[-2]+1=正無窮。

豈不是矛盾？

這種用轉移方程無法計算，但是又實際存在的情況，就必須通過手動定義。

這里手動強制定義初始條件為：F[0]=0.

而從0之后的數值是沒矛盾的，比如F[1]= F[1-2]+1= F[-1]+1=正無窮（正無窮加任何數結果還是正無窮）；F[2]= F[2-2]+1= F[0]+1=1……

第四步，確定計算順序并計算求解

那么開始計算時，是從F[1]、F[2]開始呢？還是從F[27]、F[26]開始呢？

判斷計算順序正確與否的原則是：當我們要計算F[X]（等式左邊，如F[10]）的時候，等式右邊（f[X-2], f[X-5], f[X-7]等）都是已經得到結果的狀態，這個計算順序就是OK的。

實際就是從小到大的計算方式（偶有例外的情況我們后邊再講）。

例如我們算到F[12]的時候，發現F[11]、F[10]、F[9]都已經算過了，這種算法就是對的；而開始算F[27]的時候，發現F[26]還沒有算，這樣的順序就是錯的。

很顯然這樣的情況下寫一個FOR循環就夠了。

回到這道題，采用動態規劃的算法，每一步只嘗試三種硬幣，一共進行了27步。算法時間復雜度（即需要進行的步數）為27*3。

與遞歸相比，沒有任何重復計算。

**原題練習及實際代碼：**這道題是lintcode編號669的Coin Change問題。代碼如下：

public int coinChange(int[] A, int M){// A = [2,5,7]// M = 27int[] f = new int[M + 1];int n = A.length; // 硬幣的種類// 初始化, 0個硬幣f[0] = 0;// f[1], f[2], ... , f[27] = Integer.MAX_VALUEfor (int i = 1; i <= M; i++){f[i] = Integer.MAX_VALUE;}for (int i = 1; i <= M; i++){// 使用第j個硬幣 A[j]// f[i] = min{f[i-A[0]]+1, ... , f[i-A[n-1]]+1}for (int j = 0; j < n; ++j){// 如果通過放這個硬幣能夠達到重量iif (i >= A[j] && f[i - A[j]] != Integer.MAX_VALUE) {// 獲得i的重量的硬幣數就可能是獲得i-A[j]重量硬幣數的方案+1// 拿這個方案數量與原本的方案數打擂臺，取最小值就行f[i] = Math.min(f[i - A[j]] + 1, f[i]);}}}if (f[M] == Integer.MAX_VALUE){return -1;}return f[M];}

最后總結：

1、這是求最值問題，用動態規劃方式求解。2、進入求解過程，先確定問題狀態

• 提煉最后一步
  （最優策略中使用的最后一枚硬幣aK）
  -子問題轉化 （最少的硬幣拼出更小的面值27-aK）
  3、構建轉移方程 f[X] = min{f[X-2]+1, f[X-5]+1, f[X-7]+1}
  （求min是因為題目要求求最小）
  4、設置初始條件和邊界情況 f[0] = 0, 如果不能拼出Y，f[Y]=正無窮
  5、確定計算順序并計算求解
  f[0], f[1], f[2]……

實際上按照以上4步套路，基本上可以應對絕對大多數的動態規劃面試題。

總結

在這里，由于面試中MySQL問的比較多，因此也就在此以MySQL為例為大家總結分享。但是你要學習的往往不止這一點，還有一些主流框架的使用，Spring源碼的學習，Mybatis源碼的學習等等都是需要掌握的，我也把這些知識點都整理起來了，有需要的朋友可以**【轉發+關注】后點擊這里免費領取！**

等都是需要掌握的，我也把這些知識點都整理起來了，有需要的朋友可以**【轉發+關注】后點擊這里免費領取！**

[外鏈圖片轉存中…(img-OtYDajkq-1625571563748)]