算法手劄：動态規劃

Time：2021-5-9

前言

手劄，是親手寫的書信，我寫的這裡自然沒有這個意思，隻是湊個名字比較好聽，嘿嘿。

突然開始學習算法。一切都是從LeetCode的一道題說起(題名：解碼方法)，使用遞歸無論如何優化最終都是超過限制時間，一直無法通過，一看官方答案：“動态規劃”，很好，是我沒見過的東西，于是就開始了算法的學習(流下了菜雞的淚水)。看了一晚上的背包問題，最終得出結論：算法什麼的是學不會的了。現在越學越覺得要好好考慮是否要準備轉計算機，還是繼續混電氣好qwq。

以下程式設計均使用C++來實作。

文章前面記錄動态規劃算法的一些理論描述，後面記錄題目與我的解題思路，為的是可以在日後需要再次複習時可以快速重新學一次和回想起來。

轉載請注明出處！！！

Author：霧雨霜星

歡迎來我的個人網站進行學習：

https://www.shuangxing.top/#/passage?id=21

動态規劃算法

概念：

我的了解是：

把一個問題分按照多個階段分為多個子問題，通過求解并記錄子問題的解，結合前面所得的子問題的解最終得到原問題的解。

每個子問題是整個問題中的一個階段，往往與前面狀态的子問題有關，他們之間的關系就是狀态轉移方程。

子問題與原問題是相似的，隻是子問題所需要考慮的對象隻有一部分。

采用記憶化搜尋，記錄子問題的解，不對子問題做重複解答。

進一步描述，就是對于一個事件A，分解為許多小事件Ai(i=1,2,3…)，而An的狀态可以由所有前面的子事件的狀态Ak(k=1,2,3…,n-1)決定。從Ak(k=1,2,3…,n-1)得到An的方法就是狀态轉移方程，而根據所有的事件狀态可以得到事件A的狀态。

與其說是算法，這更加像是一種解題方法。

一般的做法：
1. 确定問題的邊界條件。即在某種特殊狀況下可以直接得到問題的解。
2. 把原問題劃分為子問題。對于原問題，其過程必然是由一些列重複的子過程組合而成的，每個子過程的執行結果都可以由在前面所有的子過程執行的結果來決定。
3. 确定狀态轉移方程。即每個子問題如何根據之前所有執行的結果來進行解決。

背包問題

問題描述如下：

背包問題: 
在N件物品中取出若幹件放在容量為W的背包裡。每件物品的體積為w1,w2……,wn（wi 均為整數），各物塊相對應的價值為p1,p2……,pn（pi為整數），求背包能夠容納的最大價值。

動态規劃算法的思路：

問題分析：

問題中描述了一個事件：把若幹物塊放入到背包，有很多種組合方法，最終背包中所有物塊價值總和為最大。這個事件的過程就是放入物塊組成的，對于每個物塊，考慮放入與不放入，最終全部考慮完畢，得到背包容納最大價值。

如果這些wi與pi都給定，那就存在某種組合使得背包可以容納最大價值。但是我們不需要給出這個組合，隻需給出最大價值。

算法過程：

确定邊界條件：沒有明确的可以直接确定解的狀況(不考慮全部物塊體積為0和全部物塊體積都比背包體積大)。
确定子事件：對于物塊1,2,3…,i，在背包體積上限為j的狀況下，背包的最大容納價值。 (0≤i≤N,0≤j≤W)
确定狀态轉移方程：

如果在背包體積為j-wi下背包容納的最大的價值與pi的和比背包體積為j時最大的價值更大，那就放入，否則不放入。

包體積為j時考慮第i個物塊的最大價值 = max{ 包上限為j時考慮第i-1個物塊的最大價值, 包上限為j-wi時考慮第i-1個物塊的最大價值 + pi}

為什麼是這樣的，因為如果第i個物塊要放進去，那麼背包j>wi而且在j-wi時放入其餘物塊到背包有最大價值。

//定義二維數組dp[i][j],表示背包體積為j時,考慮1,2,3…,i物塊時最大容納價值

//狀态轉移方程:

dp[i][j]=max{dp[i-1][j],dp[i-1][j=w[i]]+p[i]}

4. 分析：

假如已經知道最終通過組合物塊k1,k2,k3...,kn可以得到背包容納最大價值。那麼在背包體積為W-kn時，不考慮物塊kn，背包最大容納價值的方法是k1,k2,k3...,kn-1組合。同理，在在背包體積為W-kn-kn-1時,不考慮物塊kn與kn-1，背包最大容納價值的方法是k1,k2,k3...,kn-2組合......

但是，我們無需給出組合方法，隻需要知道，在背包體積為W，考慮放入與不放入物塊kn可以得到最大背包容納價值，如果放入，意味着背包空間最多隻使用 了W-Kn，此時可以放入kn，放入之後的價值是：背包體積使用到最多W-kn時的價值+kn物塊的價值，而為了尋找最大的價值，是以應該是：背包體積使用到最多W-kn時的最大容納價值+kn的價值。同時比較，當不放入物塊kn，即背包體積考慮了物塊1,2,3...n-1後使用最大體積為W時的容納的價值。同理，背包體積使用到最多W-kn時的最大容納價值，是比較了kn-1後的最大容納價值，即：背包上限為W-kn-kn-1時不考慮kn與kn-1背包容納的最大價值與kn-1價值之和，與，背包上限為W-kn時不考慮kn與kn-1背包容納的最大價值，之間比較得到的較大值。

可見，給出：1.背包體積上限為 j，考慮了i-1個物塊時的最大容納價值。與，2.背包體積上限為 j-wi，考慮了i-1個物塊時的最大容納價值。再由第i個物塊的價值vi，就可以得到背包體積上限為 j，考慮了i個物塊時的最大容納價值。那麼一直推導，到最後就可以确定，背包體積上限為 W，考慮了N個物塊時的最大容納價值。

是以，如果可以确定每個狀态下背包的最大價值，那麼就可以确定背包的最終最大價值。

從上面的分析也看出了，子問題是：在考慮了i個物塊後，背包體積上限為j時的最大容納價值。

按照為了得到每個子問題的解，最大容納價值，可以确定狀态轉移方程：dp[i][j]=max{dp[i-1][j],dp[i-1][j=w[i]]+p[i]}。

而我們最終的分解是：

事件A(W, N)：背包體積為W且考慮物塊N後最大容納價值。分解為，一系列事件A(i , j)：背包體積為 j且考慮物塊 i後最大容納價值。

與我上述動态規劃算法的了解中的說法一緻。

解答方法：

public static int PackageSolution(int w[],int p[],int PackageVolume){//w[]每個元素均為整數，p[]每個元素均為整數，PackageVolume是非0整數
    int const BlockNum = sizeof(w)/4; //确定物塊數量; int占4位元組
    //定義用于存儲每個子問題的解的數組
    int **dp;
    dp = new int*[BlockNum+1];
    for(int i=0;i<=BlockNum;i++)dp[i] = new int[PackageVolume+1];
    for(int i=0;i<=BlockNum;i++){
        for(int j=0;j<=PackageVolume;j++){
                dp[i][j]=0;
        }
    }
    for(int i=1;i<=BlockNum;i++){
        for(int j=1;j<=PackageVolume;j++){
            if(j>=w[i]){
                /*
                放入物塊，則得到背包價值：考慮了i-1個物塊後背包體積上限為j-w[i]的最大容納價值 + 物塊i價值p[i]
                不放入物塊，則得到背包價值：考慮了i-1個物塊後背包體積上限為j的最大容納價值
                dp[i][j]:考慮了i個物塊後背包體積上限為j的最大容納價值
                */
                dp[i][j]=max(dp[i-1][j], dp[i-1][j-w[i]]+p[i]);
            }
           else{
               //由于放不下物塊，與不放入物塊的最大容納價值相同。
               dp[i][j]=dp[i-1][j]; 
           }
        }
    }
    return dp[BlockNum][PackageVolume];
}

因為動态規劃算法核心思想是減少重複計算，需要采用記憶化搜尋，是以每次子問題的解都要記錄下來。

考慮到對體積處理，采用所有上限均考慮的方法。

如下，使用滾動數組，即建立一維數組解決背包問題。

public static int PackageSolution(int w[],int p[],int PackageVolume) {
		//設定一個二維數組，橫坐标代表從第一個物品開始放到第幾個物品，縱坐标代表背包還有多少容量，dp代表最大價值
        int const BlockNum = sizeof(w)/4;
		int dp[] = new int[PackageVolume+1];
		for(int i=1;i<=BlockNum;i++){
            //dp[i][j]的值隻與dp[i-1][0,...,j-1]有關，是以上一次的dp[j+1,...,PackageVolume]都可以放棄
            //j 要逆向遞減(逆向枚舉)，防止上一層循環的dp[0,...,j-1]被覆寫
			for(int j=PackageVolume;j>0;j--){
				if(j>w[i]){
					dp[j] = Math.max(dp[j], dp[j-w[i]]+p[i]);
				}else{
					dp[j] = dp[j];
				}
			}
		}
		return dp[PackageVolume];

對于背包問題，采用暴力枚舉，無疑需要大量的重複計算和判斷。

第i件物品裝入或者不裝入而獲得的最大價值完全可以由前面i-1件物品的最大價值決定，暴力枚舉忽略了這個事實。

動态規劃之背包問題系列:https://tangshusen.me/2019/11/24/knapsack-problem/

解碼方法

問題描述如下：

一條包含字母 A-Z 的消息通過以下映射進行了 編碼:
'A' -> 1
'B' -> 2
...
'Z' -> 26

要 解碼 已編碼的消息，所有數字必須基于上述映射的方法，反向映射回字母（可能有多種方法）。例如，"11106" 可以映射為：
"AAJF" ，将消息分組為 (1 1 10 6); "KJF" ，将消息分組為 (11 10 6)
注意，消息不能分組為  (1 11 06) ，因為 "06" 不能映射為 "F" ，這是由于 "6" 和 "06" 在映射中并不等價。

給你一個隻含數字的 非空 字元串 s ，請計算并傳回 解碼 方法的 總數 。
題目資料保證答案肯定是一個 32 位 的整數。

來源：力扣（LeetCode）
連結：https://leetcode-cn.com/problems/decode-ways

動态規劃算法思路：

算法過程：
1. 确定邊界條件：
  
  如果s第一個字元是0，則無解碼方法。即：if(s[0]==‘0’)return 0;
2. 确定子問題：
  
  s[0,…,i]的字元串的解碼方法數量。
3. 确定狀态轉移方程：
  
  s[0,…,i-1]共有N1種解碼方法。s[0,…,i-2]共有N2種解碼方法。
  
  隻考慮把s[i]作為一個字元解碼，則s[0,…,i]共有N1種解碼方法。
  
  隻考慮把s[i-1]s[i]合并作為一個字元，則s[0,…,i]共有N2種解法。(s[i-1]==1 || (s[i-1]==2&&s[i]<=6))。
  
  若上述兩個均成立，則s[0,…,i]共有N1+N1種解法。
  
  對于s[i+1]=='0’的狀況，隻允許s[i]解碼為一個字元，不可以考慮把s[i-1]s[i]合并作為一個字元。
4. 分析：
  
  輸入字元串如果第一個字元為0，或者中間存在前面字元不是1或2的0字元，那麼就沒有解碼方法。
  
  如果采用遞歸，本質其實就是暴力枚舉，因為每檢查到一個字元，就需要把後面所有字元檢查一次，是以相當于重複檢查了很多次。
  
  我感覺，就我個人而言，要直接看出這道題目使用動态規劃，需要自己做過很多題，知道這一類的固定的組合的題目，适合使用動态規劃算法，否則，如果不能及時意識到：i長度的字元串的解碼方法可以由i+1長度的字元串的解碼方法确定，那麼就很難想到動态規劃了。

解答方法：

class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();
        if(s[0]=='0')return 0;
        if(n==1)return 1;
        int* dp=new int[n];
        dp[0]=1;
        for(int i=1;i<n;i++){
            if(s[i]=='0'){
                if(s[i-1]=='1'||s[i-1]=='2')dp[i]=dp[i-1];
                else return 0;
            }
            else{
                if(s[i-1]=='1' || (s[i-1]=='2'&&s[i]<='6')){
                    if(i<n-1&&s[i+1]=='0')dp[i]=dp[i-1];
                    else if(i>1)dp[i]=dp[i-1]+dp[i-2];
                    else dp[i]=dp[i-1]+1;
                }
                else dp[i]=dp[i-1];
            }
        }
        return dp[n-1];
    }
};

錯誤思路：

我采用的是遞歸方法，即一個函數f(s,i)，每次檢查s[i]，根據s[i]的狀況來進行if else分開讨論。設定一個變量a用于統計方法數，如果i+1存在就會遞歸去檢查s[i+1]。

會出現超出時間限制的狀況。源代碼未保留可惜了。

零錢兌換

問題描述如下:

給定不同面額的硬币 coins 和一個總金額 amount。編寫一個函數來計算可以湊成總金額所需的最少的硬币個數。如果沒有任何一種硬币組合能組成總金額，傳回 -1。
你可以認為每種硬币的數量是無限的。
資料類型：coins是整形數組，amount是整形數字。(coins[i]>0,amount>=0)

來源：力扣（LeetCode）
連結：https://leetcode-cn.com/problems/coin-change

動态規劃算法步驟：

子問題：在不同金額下考慮的兌換最小數。
邊界條件：amount==0或者coins的長度為1。
解答方法：
```
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int Max = amount + 1;
        vector<int> dp(amount + 1, Max);
        dp[0] = 0;
        for (int i = 1; i <= amount; ++i) {
            for (int j = 0; j < (int)coins.size(); ++j) {
                if (coins[j] <= i) {
                    dp[i] = min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
};

作者：LeetCode-Solution
連結：https://leetcode-cn.com/problems/coin-change/solution/322-ling-qian-dui-huan-by-leetcode-solution/
來源：力扣（LeetCode）
           
```
使用一個循環疊代每種可能出現的餘額amount，然後在每種可能出現的餘額dp[i]中疊代每種面額，讨論每種面額是否放入。這裡巧妙的是不需要但單獨通過循環來尋找每種面額放入的數量，而是在每次餘額的疊加中進行面額的循環，每次讨論是否放入某種面額coins[j]時，回溯到可以放入該面額的餘額的狀态dp[i - coins[j]]中的時候，前面的最小數量可能已經包括了這個面額。這樣就可以記錄每種餘額狀态下的最小兌換數了。

這個解答思路很聰明，初始化所有元素為amount+1，把dp[0]設定為0，友善後面的比較以及疊代到相應餘額的時候知道是否已經讨論過了。

我的思路的問題：

我也采用了動态歸還算法，但是我的做法卻超出了時間限制。代碼如下：

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        if(amount==0)return 0;
        int const num = coins.size();
        if(num==1){
            if(amount%coins[0]==0){
                return amount/coins[0];
            } 
            else return -1;
        }
        int **dp;
        dp = new int*[num+1];
        for(int i=0;i<=num;i++)dp[i] = new int[amount+1];
        for(int i=0;i<=num;i++){
            for(int j=0;j<=amount;j++){
                dp[i][j]=0;
            }
        }
        for(int i=1;i<=num;i++){
            for(int j=1;j<=amount;j++){
                if(j>=coins[i-1]){
                    int x = j/coins[i-1];
                    int temp=0;//用于尋找在判斷是否放入某種面額時，放入該指定面額不同數量下的最小的兌換數
                    for(int n=1;n<=x;n++){
                        //首先考慮是否可行
                        if(dp[i-1][j-n*coins[i-1]]==0){
                            if(j-n*coins[i-1]==0){ //對于給定j,複合此條件，那麼其他n的時候必然不成立
                                if(temp==0 || n<temp)temp=n;
                                else continue;
                            }
                            else continue;
                        }
                        else if(temp==0 || dp[i-1][j-n*coins[i-1]]+n<temp)temp=dp[i-1][j-n*coins[i-1]]+n;
                        else continue;
                    }
                    if(dp[i-1][j]==0)dp[i][j]=temp;
                    else if(temp!=0 && temp<dp[i-1][j])dp[i][j]=temp;
                    else dp[i][j]=dp[i-1][j];
                }
                else dp[i][j]=dp[i-1][j];
            }
        }
        if(dp[num][amount]==0)return -1;
        else return dp[num][amount];
    }
};

存在這樣的幾個問題。

首先是關于初始化。我對數組中每個元素的初始化是0，即代表在餘額為j，隻考慮使用前面i種面額的最小數量為0。這樣初始化在執行

dp[i-1][j-n*coins[i-1]]+n

的時候會比較友善，但是對于判斷這個方法到底是0還是無解，是未經讨論還是讨論後無解，帶來多種可能，是以需要額外大量的if語句。

然後是采用了對每種面額使用多少，進行具體讨論，即我的代碼中的n循環語句，在這個以int x = j/coins[i-1];為極限的for循環語句中，尋找使用該面額不同數量的時候最小的兌換數，存放到temp變量中，與不使用該面額的狀況進行比較。這裡重複計算的部分就是，尋找使用某種面額的數量，這個部分的确定，完全是多餘的。

我忽略了一個重要的事實：在子問題解中，讨論面額coins[i]的時候，coins[i]可能已經使用了。

我相當于把前面是否使用這個面額再讨論了一次。

總結

題目特點：
- 最終的解存在最優的子結構解
- 帶有限制條件的固定組合方式
隻要題目是存在這樣的特點，都可以優先考慮使用使用動态規劃進行處理。

通過尋找最佳子結構解，可以确定子問題，進而确定遞推關系。
處理過程避免重複計算：

主要是，往往題目不會要求給出具體的解的結構，是以在疊代過程中可以忽略具體使用了哪一個進行組合。

比如：背包問題，不需要具體知道放入物塊的W；解碼方法，不需要隻帶目前具體是如何劃分來組合；零錢兌換，不需要具體知道使用面額。

是以，在疊代過程中，對限制條件是通過+1的方法（步長為1）來子問題的解，隻需要知道目前是否符合條件，與之前進行比較，滿足最優即可。

比如：背包問題，背包空間每次+1，部分物塊下，比較目前物塊是否可以放入，若可，則比較放入後與不放之間哪個更好；零錢兌換，每次餘額+1，所有面額下，比較目前面額是否可以使用，若可，則比較使用與不使用哪個更加好。

區分上述的背包問題與零錢兌換，一個中重要的差別：背包問題中物塊每次隻可以放一個；零錢兌換中每種面額可以放多個。這種差異也造就了兩者尋找子問題解的方法不一樣，背包問題：每種物塊在各種體積下是否放入一個；零錢兌換：每次餘額增加下讨論各種面額是否使用。

兩者上述尋找子問題解的過程的差別，對應的也是子問題解的結構差別：背包問題，對于最優解，在放入最後一個物塊之前，不考慮那個物塊與那部分體積下已經有最大價值。零錢兌換，在使用最後一個硬币時，不考慮餘下的額度，考慮所有面額的紙币，已經有最小兌換數。

總而言之，如下：
- 采用記憶化搜尋，設定數組儲存每個子問題的解。
- 不讨論具體的實作方案。
子問題求解過程：

如果限制每種内容組合隻使用一次，疊代組合的内容，每種組合内容物體都疊代一次限制條件，每次限制條件步長增加(常用+1)。

如果限制每種内容組合可以使用多次，疊代限制條件，每次限制條件步長增加(常用+1)，疊代組合的内容。

轉載請注明出處！！！

Author：霧雨霜星

歡迎來我的個人網站進行學習：

https://www.shuangxing.top/#/passage?id=21

Thanks！

PS: 畢竟，霜星醬水準有限，如果發現任何錯誤還請及時郵箱告知我，我會去改哦！

算法手劄：動态規劃算法手劄：動态規劃

算法手劄：動态規劃

動态規劃算法

背包問題

解碼方法

零錢兌換

總結

繼續閱讀

[轉]ISUP信令的IAM消息詳細内容

swmm與lisflood-fp源碼如何一起編譯 CMake指令

Windows下VS開發環境環境安裝工程項目設定關于Debug和Release的提示

一文看懂字元串的加減乘除

C++ 第十五周報告1--《冒泡法排序》

HDU 1160 FatMouse's Speed （記錄路徑的最長上升子序列）

C++實作簡單順序表

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

C經典書籍筆記——C陷阱與缺陷②(文法陷阱之優先級)一、錯誤案列二、優先級規律

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

線性表之順序表的實作

C++判斷素數、求最大公約數代碼判斷一個數是否為素數求兩個數的最大公約數

SequoiaDB巨杉資料庫C++驅動概述

Linux裝置模型（中）之上層容器