您可能感興趣的文章推薦 💜《夜深人靜寫演算法》💜

前言

??很多人加我都是想詢問如何學好演算法，我的方法是我用了 十年 的時間，自己總結出來的，不可能適合所有人，但是我覺得挺有效的，如果你覺得可行，盡管一試！
??首先，我們心中要有一團🔥火🔥，一團希望之🔥火🔥！只要你心中充滿希望，即使是死去的意志也會在你內心復活，
??你永遠無法彌補你的過去，但是，你可以改變你的未來！就算暗淡無光的塵土，也會有爆發光芒的那一刻！抓住那塵埃中的剎那光輝，燃燒自己吧！

<iframe id="poz375gh-1633529776052" src="https://player.bilibili.com/player.html?aid=975999637" allowfullscreen="true" data-mediaembed="bilibili"></iframe>

?? 「 動態規劃 」作為演算法中一塊比較野的內容，沒有比較系統的分類，只能通過不斷總結歸納，對各種型別進行歸類， 「 動態規劃 」（即 Dynamic programming，簡稱 DP）是一種在數學、管理科學、計算機科學 以及 生物資訊學中使用的，通過把原問題分解為相對簡單的 「 子問題 」的方式求解 「 復雜問題 」的方法，
?? 「 動態規劃 」是一種演算法思想：若要解一個給定問題，我們需要解其不同部分（即 「 子問題 」），再根據 「 子問題 」的解以得出原問題的解，要理解動態規劃，就要理解 「 最優子結構 」 和 「 重復子問題 」，
??本文將針對以下一些常用的動態規劃問題，進行由淺入深的系統性講解，首先來看一個簡單的分類，也是今天本文要講的內容，

點擊我跳轉末尾 獲取 粉絲專屬 《演算法和資料結構》原始碼，以及獲取博主的聯系方式，

一、遞推問題

??遞推問題作為動態規劃的基礎，是最好掌握的，也是必須掌握的，它有點類似于高中數學中的數列，通過 前幾項的值 推匯出 當前項的值，

1、一維遞推

??你正在爬樓梯，需要 n n n 階你才能到達樓頂，每次你可以爬 1 1 1 或 2 2 2 個臺階，你有多少種不同的方法可以爬到樓頂呢？

??假設我們已經到了第 n n n 階樓梯，那么它可以是從 n ? 1 n-1 n?1 階過來的，也可以是從 n ? 2 n-2 n?2 階過來的（但是，不可能是從 n ? 3 n-3 n?3 階直接過來的），所以如果達到第 n n n 階的方案數為 f [ n ] f[n] f[n]，那么到達 n ? 1 n-1 n?1 階就是 f [ n ? 1 ] f[n-1] f[n?1]，到達 n ? 2 n-2 n?2 階 就是 f [ n ? 2 ] f[n-2] f[n?2]，所以可以得出： f [ n ] = f [ n ? 1 ] + f [ n ? 2 ] f[n] = f[n-1] + f[n-2] f[n]=f[n?1]+f[n?2]??其中，當 n = 0 n=0 n=0 時方案數為 1，代表初始情況； n = 1 n=1 n=1 時方案數為 1，代表走了一步，遞推計算即可，
??以上就是最簡單的動態規劃問題，也是一個經典的數列：斐波那契數列 的求解方式，它通過一個遞推公式，將原本指數級的問題轉化成了線性的，時間復雜度為 O ( n ) O(n) O(n)，
??C語言代碼實作如下：

int f[1000];
int climbStairs(int n){
    f[0] = f[1] = 1;
    for(int i = 2; i <= n; ++i) {
        f[i] = f[i-1] + f[i-2];
    }
    return f[n];
}

2、二維遞推

??給定一個非負整數 n n n，生成楊輝三角的前 n n n 行，在楊輝三角中，每個數是它 左上方 和 右上方 的數的和，

??根據楊輝三角的定義，我們可以簡單將上面的圖進行一個變形，得到：

于是，我們可以得出以下結論：
??1）楊輝三角的所有數可以存盤在一個二維陣列中，行代表第一維，列代表第二維度；
??2）第 i i i 行的元素個數為 i i i 個；
??3）第 i i i 行 第 j j j 列的元素滿足公式： c [ i ] [ j ] = { 1 i = 0 c [ i ? 1 ] [ j ? 1 ] + c [ i ? 1 ] [ j ] o t h e r w i s e c[i][j] = \begin{cases} 1 & i=0\\ c[i-1][j-1] + c[i-1][j] & otherwise \end{cases} c[i][j]={1c[i?1][j?1]+c[i?1][j]?i=0otherwise?
??于是就可以兩層回圈列舉了，時間復雜度為 O ( n 2 ) O(n^2) O(n2)，
??C語言代碼實作如下：

int c[40];
void generate(int n) {
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j <= i; ++j) {
            if(j == 0 || j == i) {
                c[i][j] = 1;
            }else {
                c[i][j] = c[i-1][j-1] + c[i-1][j];
            }
        }
    }
}

二、線性DP

1、最小花費

??陣列的每個下標作為一個階梯，第 i i i 個階梯對應著一個非負數的體力花費值 c o s t [ i ] cost[i] cost[i]（下標從 0 開始），每當爬上一個階梯，都要花費對應的體力值，一旦支付了相應的體力值，就可以選擇 向上爬一個階梯 或者 爬兩個階梯，求找出達到樓層頂部的最低花費，在開始時，可以選擇從下標為 0 0 0 或 1 1 1 的元素作為初始階梯，

??令走到第 i i i 層的最小消耗為 f [ i ] f[i] f[i]，假設當前的位置在 i i i 層樓梯，那么只可能從 i ? 1 i-1 i?1 層過來，或者 i ? 2 i-2 i?2 層過來；
????如果從 i ? 1 i-1 i?1 層過來，則需要消耗體力值： f [ i ? 1 ] + c o s t [ i ? 1 ] f[i-1] + cost[i-1] f[i?1]+cost[i?1]；
????如果從 i ? 2 i-2 i?2 層過來，則需要消耗體力值： f [ i ? 2 ] + c o s t [ i ? 2 ] f[i-2] + cost[i-2] f[i?2]+cost[i?2]；
??起點可以在第 0 或者 第 1 層，于是有狀態轉移方程： f [ i ] = { 0 i = 0 , 1 min ? ( f [ i ? 1 ] + c o s t [ i ? 1 ] , f [ i ? 2 ] + c o s t [ i ? 2 ] ) i > 1 f[i] = \begin{cases} 0 & i=0,1\\ \min ( f[i-1] + cost[i-1], f[i-2] + cost[i-2] ) & i > 1\end{cases} f[i]={0min(f[i?1]+cost[i?1],f[i?2]+cost[i?2])?i=0,1i>1?

??這個問題和一開始的遞推問題的區別在于：一個是求前兩項的和，一個是求最小值，這里就涉及到了動態取舍的問題，也就是動態規劃的思想，
??如果從前往后思考，每次都有兩種選擇，時間復雜度為 O ( 2 n ) O(2^n) O(2n)，轉化成動態規劃以后，只需要一個回圈，時間復雜度為 O ( n ) O(n) O(n)，
??C語言代碼實作如下：

int f[1024];
int min(int a, int b) {
    return a < b ? a : b;
}
int minCostClimbingStairs(int* cost, int costSize){
    f[0] = 0;
    f[1] = 0;
    for(int i = 2; i <= costSize; ++i) {
        f[i] = min(f[i-1] + cost[i-1], f[i-2] + cost[i-2]);
    }
    return f[costSize];
}

2、最大子段和

??給定一個整數陣列 n u m s nums nums ，找到一個具有最大和的連續子陣列（子陣列最少包含一個元素），回傳其最大和，

??由于要求的是連續的子陣列，所以對于第 i i i 個元素，狀態轉移一定是從 i ? 1 i-1 i?1 個元素轉移過來的，基于這一點，可以令 f [ i ] f[i] f[i] 表示以 i i i 號元素結尾的最大值，
??那么很自然，這個最大值必然包含 n u m s [ i ] nums[i] nums[i] 這個元素，那么要不要包含 n u m s [ i ? 1 ] , n u m s [ i ? 2 ] , n u m s [ i ? 3 ] , . . . , n u m s [ k ] nums[i-1],nums[i-2],nums[i-3],...,nums[k] nums[i?1],nums[i?2],nums[i?3],...,nums[k] 呢？其實就是看第 i ? 1 i-1 i?1 號元素結尾的最大值是否大于零，也就是：當 f [ i ? 1 ] ≤ 0 f[i-1] \le 0 f[i?1]≤0 時，則 前 i ? 1 i-1 i?1 個元素是沒必要包含進來的，所以就有狀態轉移方程： f [ i ] = { n u m s [ 0 ] i = 0 n u m s [ i ] f [ i ? 1 ] ≤ 0 n u m s [ i ] + f [ i ? 1 ] f [ i ? 1 ] > 0 f[i] = \begin{cases} nums[0] & i = 0 \\ nums[i] & f[i-1] \le 0 \\ nums[i] + f[i-1] & f[i-1] > 0\end{cases} f[i]=??????nums[0]nums[i]nums[i]+f[i?1]?i=0f[i?1]≤0f[i?1]>0?一層回圈列舉后，取 m a x ( f [ i ] ) max(f[i]) max(f[i]) 就是答案了，只需要一個回圈，時間復雜度為 O ( n ) O(n) O(n)，
??C語言代碼實作如下：

int dp[30010];
int max(int a, int b) {
    return a > b ? a : b;
}

int maxSubArray(int* nums, int numsSize){
    int maxValue = nums[0];
    dp[0] = nums[0];
    for(int i = 1; i < numsSize; ++i) {
        dp[i] = nums[i];
        if(dp[i-1] > 0) {
            dp[i] += dp[i-1];
        }
        maxValue = max(maxValue, dp[i]);
    }
    return maxValue;
}

3、最長單調子序列

??給定一個長度為 n ( 1 ≤ n ≤ 1000 ) n(1 \le n \le 1000) n(1≤n≤1000) 的陣列 a i a_i ai?，求給出它的最長遞增子序列的長度，

??在看這個問題之前，我們先來明確一些概念：單調序列、單調子序列、最大長單調子序列，
??單調序列 就是一個滿足某種單調性的陣列序列，比如 單調遞增序列、單調遞減序列、單調不增序列、單調不減序列，舉幾個簡單的例子：
??單調遞增序列：1，2，3，7，9
??單調遞減序列：9，8，4，2，1
??單調不增序列：9，8，8，5，2
??單調不減序列：1，2，2，5，5
??一個比較直觀的單調遞增序列的例子就是一個樓梯的側面，

??我們可以把這個樓梯每一階的高度用一個數字表示，得到一個單調遞增序列，如圖所示：

??單調子序列 指的是任意一個陣列序列，按順序選擇一些元素組成一個新的序列，并且滿足單調性，對于一個長度為 n n n 的序列，每個元素可以選擇 “取” 或者 “不取”，所以最多情況下，有 2 n 2^n 2n 個單調子序列，
??如圖所示，代表的是序列：[1，2，4，6，3，5，9]

??其中 [1，2，6] 為它的一個長度為 3 的單調子序列，如圖所示；

??[1，3，6] 則不是，因為 3 和 6 的順序不是原序列中的順序；[1，4，3] 也不是，因為它不滿足單調性，
??最長單調子序列 是指對于原陣列序列，能夠找到的元素個數最多的單調子序列，
??還是以 [1，2，4，6，3，5，9] 為例，它的最長單調子序列為：[1，2，4，6，9]，長度為 5；

??當然，也可以是 [1，2，3，5，9]，長度同樣為 5， ??那么，接下來，我們看下如何通過動態規劃的方法來求解 最長遞增子序列，
??對于陣列序列 a i ( 1 ≤ i ≤ n ) a_i(1 \le i \le n) ai?(1≤i≤n)，令 f [ i ] f[i] f[i] 表示以第 i i i 個數 a i a_i ai? 結尾的最長遞增子序列的長度，那么，我們考慮以第 i i i 個數 a i a_i ai? 結尾的最長遞增子序列，它在這個序列中的前一個數一定是 a j ( 1 ≤ j < i ) a_j(1 \le j < i) aj?(1≤j<i) 中的一個，所以，如果我們已經知道了 f [ j ] f[j] f[j]，那么就有 f [ i ] = f [ j ] + 1 f[i] = f[j] + 1 f[i]=f[j]+1，顯然，我們還需要滿足 a j < a i a_j < a_i aj?<ai? 這個遞增的限制條件，
??那么就可以得出狀態轉移方程： f [ i ] = max ? j = 1 i ? 1 ( f [ j ] ∣ a j < a i ) + 1 f[i] = \max_{j=1}^{i-1} (f[j] \ | \ a_j < a_i) + 1 f[i]=j=1maxi?1?(f[j] ∣ aj?<ai?)+1??這里 f [ j ] f[j] f[j] 是 f [ i ] f[i] f[i] 的子結構，而 m a x ( f [ j ] ) max(f[j]) max(f[j]) 是 f [ i ] f[i] f[i] 的最優子結構，當然我們需要考慮一種情況，就是沒有找到最優子結構的時候，例如： i = 1 i=1 i=1 或者 不存在 a j < a i a_j < a_i aj?<ai? 的 j j j，此時 f [ i ] = 1 f[i] = 1 f[i]=1，表示 a i a_i ai? 本身是一個長度為 1 1 1 的最長遞增子序列，
?? f [ i ] f[i] f[i] 陣列可以通過兩層回圈來求解，如下圖表所示：

??狀態數 f [ . . . ] f[...] f[...] 總共 O ( n ) O(n) O(n) 個，狀態轉移的消耗為 O ( n ) O(n) O(n)，所以總的時間復雜度為 O ( n 2 ) O(n^2) O(n2)，所以對于這類問題，一般能夠接受的 n n n 的范圍在千級別，也就是 1000 , 2000 , 3000... 1000, 2000, 3000 ... 1000,2000,3000...，如果是 n = 10000 , 100000 n=10000, 100000 n=10000,100000 的情況，就需要考慮優化了，
??有關最長單調子序列的問題，還有 O ( n l o g 2 n ) O(nlog_2n) O(nlog2?n) 的優化演算法，具體方法可以參考以下文章：夜深人靜寫演算法（二十）- 最長單調子序列，

三、二維DP

1、最長公共子序列

??給定兩個陣列序列 a 1 , a 2 , . . . , a n a_1, a_2, ..., a_n a1?,a2?,...,an? 和 b 1 , b 2 , . . . , b m b_1, b_2, ..., b_m b1?,b2?,...,bm?，其中 n , m ≤ 1000 n,m \le 1000 n,m≤1000，求兩個陣列的最長公共子序列，

??考慮兩個陣列序列 a 1 , a 2 , . . . , a n a_1, a_2, ..., a_n a1?,a2?,...,an? 和 b 1 , b 2 , . . . , b m b_1, b_2, ..., b_m b1?,b2?,...,bm?，對于 a a a 序列中第 i i i 個元素 a i a_i ai? 和 b b b 序列中的第 j j j 個元素 b j b_j bj?，有兩種情況：
?? ( 1 ) (1) (1) 相等即 a i = = b j a_i == b_j ai?==bj? 的情況，這個時候如果前綴序列 a 1 , a 2 , . . . , a i ? 1 a_1, a_2, ..., a_{i-1} a1?,a2?,...,ai?1? 和 b 1 , b 2 , . . . , b j ? 1 b_1, b_2, ..., b_{j-1} b1?,b2?,...,bj?1? 的最長公共子序列已經求出來了，記為 x x x 的話，那么很顯然，在兩個序列分別加入 a i a_i ai? 和 b j b_j bj? 以后，長度又貢獻了 1，所以 a 1 , a 2 , . . . , a i a_1, a_2, ..., a_{i} a1?,a2?,...,ai? 和 b 1 , b 2 , . . . , b j b_1, b_2, ..., b_{j} b1?,b2?,...,bj? 的最長公共子序列就是 x + 1 x+1 x+1；

?? ( 2 ) (2) (2) 不相等即 a i ≠ b j a_i \neq b_j ai??=bj? 的情況，這個時候我們可以把問題拆分成兩個更小的子問題，即 分別去掉 a i a_i ai? 和 b j b_j bj? 的情況，如圖所示：

??去掉 a i a_i ai? 以后，問題轉變為求： a 1 , a 2 , . . . , a i ? 1 a_1, a_2, ..., a_{i-1} a1?,a2?,...,ai?1? 和 b 1 , b 2 , . . . , b j b_1, b_2, ..., b_{j} b1?,b2?,...,bj? 的最長公共子序列；
??去掉 b j b_j bj? 以后，問題轉變為求： a 1 , a 2 , . . . , a i a_1, a_2, ..., a_{i} a1?,a2?,...,ai? 和 b 1 , b 2 , . . . , b j ? 1 b_1, b_2, ..., b_{j-1} b1?,b2?,...,bj?1? 的最長公共子序列；
??根據上面的兩種情況的討論，我們發現，在任何時候，我們都在求 a a a 的前綴 和 b b b 的前綴的最長公共序列，所以可以這么定義狀態：用 f [ i ] [ j ] f[i][j] f[i][j] 表示 a 1 , a 2 , . . . , a i a_1, a_2, ..., a_{i} a1?,a2?,...,ai? 和 b 1 , b 2 , . . . , b j b_1, b_2, ..., b_{j} b1?,b2?,...,bj? 的最長公共子序列，
??在設計狀態的程序中，我們已經無形中把狀態轉移也設計好了，狀態轉移方程如下： f [ i ] [ j ] = { 0 i = 0 o r j = 0 f [ i ? 1 ] [ j ? 1 ] + 1 i , j > 0 , a i = b j max ? ( f [ i ] [ j ? 1 ] , f [ i ? 1 ] [ j ] ) i , j > 0 , a i ≠ b j f[i][j] = \begin{cases}0 & i=0\ or\ j=0 \\ f[i-1][j-1] + 1 & i,j>0,a_i=b_j \\ \max(f[i][j-1], f[i-1][j]) & i,j>0,a_i \neq b_j\end{cases} f[i][j]=??????0f[i?1][j?1]+1max(f[i][j?1],f[i?1][j])?i=0 or j=0i,j>0,ai?=bj?i,j>0,ai??=bj????對于 i = 0 i=0 i=0 或者 j = 0 j=0 j=0 代表的是：其中一個序列的長度為 0，那么最長公共子序列的長度肯定就是 0 了；
??其余兩種情況，就是我們上文提到的 a i a_i ai? 和 b j b_j bj? “相等” 與 “不相等” 的兩種情況下的狀態轉移，如圖所示，代表了字串 “GATCGTGAGC” 和 “AGTACG” 求解最長公共子序列的 f [ i ] [ j ] ( i , j > 0 ) f[i][j] (i,j > 0) f[i][j](i,j>0) 的矩陣，

??對于長度分別為 n n n 和 m m m 的兩個序列，求解它們的最長公共子序列時，狀態數總共有 O ( n m ) O(nm) O(nm) 個，每次狀態轉移的消耗為 O ( 1 ) O(1) O(1)，所以總的時間復雜度為 O ( n m ) O(nm) O(nm)，
??對于 f [ i ] [ j ] f[i][j] f[i][j] 這個狀態，求解程序中，只依賴于 f [ i ] [ j ? 1 ] f[i][j-1] f[i][j?1]、 f [ i ? 1 ] [ j ? 1 ] f[i-1][j-1] f[i?1][j?1]、 f [ i ? 1 ] [ j ] f[i-1][j] f[i?1][j]，

??即每次求解只需要有 上一行 和 這一行 的狀態即可，所以可以采用滾動陣列進行優化，將狀態轉移方程變成： f [ c u r ] [ j ] = { f [ l a s t ] [ j ? 1 ] + 1 j > 0 , a i = b j max ? ( f [ c u r ] [ j ? 1 ] , f [ l a s t ] [ j ] ) j > 0 , a i ≠ b j f[cur][j] = \begin{cases}f[last][j-1] + 1 & j>0,a_i=b_j \\ \max(f[cur][j-1], f[last][j]) & j>0,a_i \neq b_j\end{cases} f[cur][j]={f[last][j?1]+1max(f[cur][j?1],f[last][j])?j>0,ai?=bj?j>0,ai??=bj????只需要簡單將 i i i 替換成 c u r cur cur， i ? 1 i-1 i?1 替換成 l a s t last last 即可，這樣就把原本 O ( n m ) O(nm) O(nm) 的空間復雜度變成了 O ( p ) O(p) O(p)，其中 p = min ? ( n , m ) p = \min(n,m) p=min(n,m)，

• 優化后的 C++ 代碼實作如下：

typedef char ValueType;
const int maxn = 5010;
int f[2][maxn];

int getLCSLength(int hsize, ValueType *h, int vsize, ValueType *v) {
    memset(f, 0, sizeof(f));
    int cur = 1, last = 0;
    for (int i = 1; i <= vsize; ++i) {
        for (int j = 1; j <= hsize; ++j) {
            if (v[i] == h[j])
                f[cur][j] = f[last][j - 1] + 1;
            else
                f[cur][j] = max(f[cur][j - 1], f[last][j]);
        }
        swap(last, cur);
    }
    return f[last][hsize];
}

??有關于 最長公共子序列 的更多內容，可以參考以下內容：夜深人靜寫演算法（二十一）- 最長公共子序列，

2、最小編輯距離

??長度為 n n n 的源字串 a 1 , a 2 , . . . , a n a_1,a_2,...,a_n a1?,a2?,...,an?，經過一些給定操作變成長度為 m m m 的目標字串 b 1 , b 2 , . . . b m b_1,b_2,...b_m b1?,b2?,...bm?，操作包括如下三種：
??1） I n s e r t Insert Insert：在源字串中插入一個字符，插入消耗為 I I I；
??2） D e l e t e Delete Delete：在源字串中洗掉一個字符，洗掉消耗為 D D D；
??3） R e p l a c e Replace Replace：將源字串中的一個字符替換成另一個字符，替換消耗為 R R R；
求最少的總消耗，其中 n , m ≤ 1000 n,m \le 1000 n,m≤1000，

??令 f [ i ] [ j ] f[i][j] f[i][j] 表示源字串 a 1 , a 2 , . . . , a i a_1,a_2,...,a_i a1?,a2?,...,ai? 經過上述三種操作變成目標字串 b 1 , b 2 , . . . b j b_1,b_2,...b_j b1?,b2?,...bj? 的最少消耗，
??假設 a 1 , a 2 , . . . , a i a_1,a_2,...,a_{i} a1?,a2?,...,ai? 變成 b 1 , b 2 , . . . b j ? 1 b_1,b_2,...b_{j-1} b1?,b2?,...bj?1? 的最少消耗已經求出，等于 f [ i ] [ j ? 1 ] f[i][j-1] f[i][j?1]，則需要在 a [ i ] a[i] a[i] 的后面插入一個字符 b j b_j bj?，那么產生的消耗為： f [ i ] [ j ? 1 ] + I f[i][j-1] + I f[i][j?1]+I 如圖所示，源字串為 “AGTA”，目標字符串為 “GATCGT” 的情況下，將源字串變成 "“GATCG” 的最小消耗為 f [ i ] [ j ? 1 ] f[i][j-1] f[i][j?1]，那么只要在源字串最后再插入一個 ‘T’，就可以把源字串變成目標字串 “GATCGT”；

??假設 a 1 , a 2 , . . . , a i ? 1 a_1,a_2,...,a_{i-1} a1?,a2?,...,ai?1? 變成 b 1 , b 2 , . . . b j b_1,b_2,...b_{j} b1?,b2?,...bj? 的最少消耗已經求出，等于 f [ i ? 1 ] [ j ] f[i-1][j] f[i?1][j]，則需要把 a i a_i ai? 個刪掉，那么產生的消耗為： f [ i ? 1 ] [ j ] + D f[i-1][j] + D f[i?1][j]+D 如圖所示，源字串為 “AGTA”，目標字串為 “GATCGT” 的情況下，將 “AGT” 變成目標字串的最小消耗為 f [ i ? 1 ] [ j ] f[i-1][j] f[i?1][j]，那么只要把源字串最后一個’A’刪掉，就可以把源字串變成目標字串；

??假設 a 1 , a 2 , . . . , a i ? 1 a_1,a_2,...,a_{i-1} a1?,a2?,...,ai?1? 變成 b 1 , b 2 , . . . b j ? 1 b_1,b_2,...b_{j-1} b1?,b2?,...bj?1? 的最少消耗已經求出，等于 f [ i ? 1 ] [ j ? 1 ] f[i-1][j-1] f[i?1][j?1]，則將 a i a_i ai? 替換成 b j b_j bj?， a 1 , a 2 , . . . , a i a_1,a_2,...,a_{i} a1?,a2?,...,ai? 就可以變成 b 1 , b 2 , . . . b j b_1,b_2,...b_{j} b1?,b2?,...bj?，替換時需要考慮 a i = b j a_i=b_j ai?=bj? 和 a i ≠ b j a_i \neq b_j ai??=bj? 的情況，所以替換產生的消耗為： f [ i ? 1 ] [ j ? 1 ] + { 0 a i = b j R a i ≠ b j f[i-1][j-1] + \begin{cases} 0 & a_i=b_j \\ R & a_i \neq b_j\end{cases} f[i?1][j?1]+{0R?ai?=bj?ai??=bj?? 如圖所示，源字串為 “AGTA”，目標字串為 “GATCGT” 的情況下，將 “AGT” 變成 “GATCGT” 的最小消耗為 f [ i ? 1 ] [ j ? 1 ] f[i-1][j-1] f[i?1][j?1]，那么只要將 源字串 的最后一個字符 替換為 目標字串 的最后一個字符 ，就可以把源字串變成目標字串；替換時根據 源字串 和 目標字串 原本是否相等來決定消耗；

• 邊界情況主要考慮以下幾種：
  ??a. 空串變成目標串 即 f [ 0 ] [ j ] f[0][j] f[0][j]，總共需要插入 j j j 個字符，所以 f [ 0 ] [ j ] = f [ 0 ] [ j ? 1 ] + I f[0][j] = f[0][j-1] + I f[0][j]=f[0][j?1]+I；
  ??b. 源字串變成空串 即 f [ i ] [ 0 ] f[i][0] f[i][0]，總共需要洗掉 i i i 個字符，所以 f [ i ] [ 0 ] = f [ i ? 1 ] [ 0 ] + D f[i][0] = f[i-1][0] + D f[i][0]=f[i?1][0]+D；
  ??c. 空串變成空串 即 f [ 0 ] [ 0 ] = 0 f[0][0] = 0 f[0][0]=0

??將上述所有狀態進行一個整合，得到狀態轉移方程如下： f [ i ] [ j ] = { 0 i = 0 , j = 0 f [ i ] [ j ? 1 ] + I i = 0 , j > 0 f [ i ? 1 ] [ j ] + D i > 0 , j = 0 min ? i > 0 , j > 0 { f [ i ] [ j ? 1 ] + I f [ i ? 1 ] [ j ] + D f [ i ? 1 ] [ j ? 1 ] + R a i ≠ b j f[i][j] = \begin{cases}0 & i=0,j=0\\f[i][j-1]+I & i=0,j>0\\ f[i-1][j] + D & i>0,j=0 \\ \min_{i>0,j>0} \begin{cases} f[i][j-1] + I\\ f[i-1][j] + D\\ f[i-1][j-1] + R_{a_i \neq b_j}\end{cases}\end{cases} f[i][j]=????????????????????0f[i][j?1]+If[i?1][j]+Dmini>0,j>0???????f[i][j?1]+If[i?1][j]+Df[i?1][j?1]+Rai??=bj????i=0,j=0i=0,j>0i>0,j=0
??通過這個狀態矩陣，最后計算得到 f [ n ] [ m ] f[n][m] f[n][m] 就是該題所求 "源字串 a 1 , a 2 , . . . , a n a_1,a_2,...,a_n a1?,a2?,...,an?，經過 插入、洗掉、替換 變成目標字串 b 1 , b 2 , . . . b m b_1,b_2,...b_m b1?,b2?,...bm?" 的最少消耗了，特殊的，當 I = D = R = 1 I = D = R = 1 I=D=R=1 時， f [ n ] [ m ] f[n][m] f[n][m] 就是字串 a a a 和 b b b 的萊文斯坦距離，
??狀態總數 O ( n m ) O(nm) O(nm)，每次狀態轉移的消耗為 O ( 1 ) O(1) O(1)，所以總的時間復雜度為 O ( n m ) O(nm) O(nm)，空間上可以采用滾動陣列進行優化，具體優化方案可以參考 最長公共子序列 的求解程序，
??如圖所示的是一張源字串 “AGTACG” 到目標字串 “GATCGTGAGC” 的萊文斯坦距離圖，

??有關最小編輯距離的詳細內容，可以參考：夜深人靜寫演算法（二十二）- 最小編輯距離，

3、雙串匹配問題

??給定一個 匹配字串 s (只包含小寫字母) 和一個 模式字串 p (包含小寫字母和兩種額外字符：'.'和 '*')，要求實作一個支持 '.'和 '*'的正則運算式匹配（'*'前面保證有字符），
??'.'匹配任意單個字符
??'*'匹配零個或多個前面的那一個元素

??這是個經典的 串匹配 問題，可以按照 最長公共子序列 的思路去解決，令 f ( i , j ) f(i, j) f(i,j) 代表的是 匹配串前綴 s[0:i] 和 模式串前綴 p[0:j] 是否有匹配，只有兩個值： 0 代表 不匹配， 1 代表 匹配，
??于是，對模式串進行分情況討論：
??1）當 p[j] 為.時，代表 s[i] 為任意字符時，它都能夠匹配（沒毛病吧？沒毛病），所以問題就轉化成了求 匹配串前綴 s[0:i-1] 和 模式串前綴 p[0:j-1] 是否有匹配的問題，也就是這種情況下 f ( i , j ) = f ( i ? 1 , j ? 1 ) f(i, j) = f(i-1, j-1) f(i,j)=f(i?1,j?1)，如圖1所示：


??2）當 p[j] 為*時，由于*前面保證有字符，所以拿到字符 p[j-1]，分情況討論：
????2.a）如果 p[j-1] 為.時，可以匹配所有 s[0:i] 的后綴，這種情況下，只要 f ( k , j ? 2 ) f(k, j-2) f(k,j?2) 為 1， f ( i , j ) f(i, j) f(i,j) 就為 1；其中 k ∈ [ 0 , i ] k \in [0, i] k∈[0,i]，如下圖所示：


????2.b）如果 p[j-1] 非.時，只有當 s[0:i] 的后綴 字符全為 p[j-1] 時，才能去匹配 s[0:i] 的前綴，同樣轉化成 f ( k , j ? 2 ) f(k, j-2) f(k,j?2) 的子問題，如下圖所示：


??3）當 p[j] 為其他任意字符時，一旦 p[j] 和 s[i] 不匹配，就認為 f ( i , j ) = 0 f(i, j) = 0 f(i,j)=0，否則 f ( i , j ) = f ( i ? 1 , j ? 1 ) f(i, j) = f(i-1, j-1) f(i,j)=f(i?1,j?1)，如下圖所示：


??最后，這個問題可以采用 記憶化搜索 求解，并且需要考慮一些邊界條件，邊界條件可以參考代碼實作中的講解，記憶化搜索會在下文仔細講解，
??匹配串的長度為 n n n，模式串的長度為 m m m，狀態數： O ( n m ) O(nm) O(nm)，狀態轉移： O ( n ) O(n) O(n)，時間復雜度： O ( n 2 m ) O(n^2m) O(n2m)，

四、記憶化搜索

??給定一個 n ( n ≤ 45 ) n(n \le 45) n(n≤45)，求 斐波那契數列的第 n n n 項的值，要求用遞回實作，

??那么，我們只需要套用上面的遞回函式，并且處理好遞回出口，就能把它寫成遞回的形式，C語言 代碼實作如下：

int f(unsigned int n) {
    if(n <= 1) {
        return 1;
    }
    return f(n-1) + f(n-2);
}

??遞回求解的程序如下：

??這是一棵二叉樹，樹的高度為 n n n，所以粗看遞回訪問時結點數為 2 n 2^n 2n，但是仔細看，對于任何一棵子樹而言，左子樹的高度一定比右子樹的高度大，所以不是一棵嚴格的完全二叉樹，為了探究它實際的時間復雜度，我們改下代碼：

int f(unsigned int n) {
    ++c[n];
    if(n <= 1) {
        return 1;
    }
    return f(n-1) + f(n-2);
}

??加了一句代碼 ++c[n];，引入一個計數器，來看下在不同的 n n n 的情況下， f ( n ) f(n) f(n) 這個函式的呼叫次數，如圖所示：

??觀察 c [ n ] c[n] c[n] 的增長趨勢，首先排除等引數列，然后再來看是否符合等比數列，我們來嘗試求下 c [ n ] / c [ n ? 1 ] c[n] / c[n-1] c[n]/c[n?1] 的值，列出表格如下：

??觀察發現，隨著 n n n 的不斷增大， c [ n ] / c [ n ? 1 ] c[n]/c[n-1] c[n]/c[n?1] 越來越接近一個常數，而這個常數就是黃金分割的倒數： 2 5 ? 1 ≈ 1.618034 \frac {2}{ \sqrt 5 - 1} \approx 1.618034 5 ??12?≈1.618034??當 n n n 趨近于無窮大的時候，滿足如下公式： c [ n ] = 2 5 ? 1 c [ n ? 1 ] c[n] = \frac {2}{ \sqrt 5 - 1} c[n-1] c[n]=5 ??12?c[n?1]??對等比數列化解后累乘得到： c [ n ] = 2 5 ? 1 c [ n ? 1 ] = ( 2 5 ? 1 ) 2 c [ n ? 2 ] = ( 2 5 ? 1 ) n \begin{aligned}c[n] &= \frac {2}{ \sqrt 5 - 1} c[n-1]\\ &= (\frac {2}{ \sqrt 5 - 1})^2 c[n-2]\\ &= (\frac {2}{ \sqrt 5 - 1})^n \end{aligned} c[n]?=5 ??12?c[n?1]=(5 ??12?)2c[n?2]=(5 ??12?)n???所以，斐波那契數列遞回求解的時間復雜度就是 ： O ( ( 2 5 ? 1 ) n ) O((\frac {2}{ \sqrt 5 - 1})^n) O((5 ??12?)n)
??這是一個指數級的演算法，隨著 n n n 的不斷增大，時間消耗呈指數級增長，我們在寫代碼的時候肯定是要避免這樣的寫法的，尤其是在服務器開發程序中，CPU 是一種極其寶貴的資源，任何的浪費都是可恥的，但是，面試官又要求用遞回實作，真是太討厭了！
??那么，怎么來優化這里的算力消耗呢？
??遞回求解斐波那契數列其實是一個深度優先搜索的程序，它是毫無優化的暴力列舉，對于 f ( 5 ) f(5) f(5) 的求解，如圖所示：

??同時，我們也發現，計算程序中其實有很多重疊子問題，例如 f ( 3 ) f(3) f(3) 被計算了 2 2 2 次，如圖所示：

?? f ( 2 ) f(2) f(2) 被計算了 3 3 3 次，如圖所示：

??所以如果我們能夠確保每個 f ( i ) f(i) f(i) 只被計算一次，問題就迎刃而解了，可以考慮將 f ( i ) f(i) f(i) 計算出來的值存盤到哈希陣列 h [ i ] h[i] h[i] 中，當第二次要訪問 f ( i ) f(i) f(i) 時，直接取 h [ i ] h[i] h[i] 的值即可，這樣每次計算 f ( i ) f(i) f(i) 的時間復雜度變成了 O ( 1 ) O(1) O(1)，總共需要計算 f ( 2 ) , f ( 3 ) , . . . f ( n ) f(2),f(3),...f(n) f(2),f(3),...f(n)，總的時間復雜度就變成了 O ( n ) O(n) O(n) ，
??這種用哈希陣列來記錄運算結果，避免重復運算的方法就是記憶化搜索，
??這件事情如何執行下去呢？
??我們用一個陣列 h [ i ] h[i] h[i] 來記錄 斐波那契數列 第 i i i 項的值，把之前的遞回代碼改成如下形式：

const int inf = -1;
int h[46];

void init() {
    memset(h, inf, sizeof(h));  // 1）
}

int f(unsigned int n) {
    if(n <= 1) {
        return 1;
    }
    int &fib = h[n];            // 2）
    if(fib != inf) {
        return fib;             // 3）
    }
    fib = f(n-1) + f(n-2);      // 4）
    return fib;
}

• 1）初始化所有 f ( i ) f(i) f(i) 都沒有被計算過，為了方便用 memset，可以將 inf定義成 -1；
• 2）注意這里用了個參考，而且一定要用參考，具體原因留給讀者自己思考，當然不想思考的話，下文也會講到，不必擔心；
• 3）當 fib也就是 h[n]已經計算過了，那么直接回傳結果即可；
• 4）最后，利用遞回計算h[n]的值，并且回傳結果；

??和遞回版本相比，多了這么一段代碼：

    int &fib = h[n];
    if(fib != inf) {
        return fib;
    }

??那么它的作用體現在哪里呢？我們通過一個動圖來感受一下：

??如圖所示，當第二次需要計算 f ( 2 ) f(2) f(2) 和 f ( 3 ) f(3) f(3) 時，由于結果已經計算出來并且存盤在 h [ 2 ] h[2] h[2] 和 h [ 3 ] h[3] h[3] 中，所以上面這段代碼的fib != inf運算式為真，直接回傳，不再需要往下遞回計算，這樣就把原本的 “遞回二叉樹” 轉換成了 “遞回鏈”， 從而將原本指數級的演算法變成了多項式級別，
??上文用一個簡單的例子闡述了記憶化搜索的實作方式，并且提到了利用陣列來記錄已經計算出來的重疊子問題，這個和動態規劃的思想非常相似，沒錯，記憶化搜索其實用的就是動態規劃的思想，更加確切的說，可以用如下公式來表示：

記憶化搜索 = 深度優先搜索的實作 + 動態規劃的思想
??有關記憶化搜索的更多內容，可以參考： 夜深人靜寫演算法（二十六）- 記憶化搜索，

五、背包問題

1、0/1 背包

??有 n ( n ≤ 100 ) n(n \le100) n(n≤100) 個物品和一個容量為 m ( m ≤ 10000 ) m(m \le 10000) m(m≤10000) 的背包，第 i i i 個物品的容量是 c [ i ] c[i] c[i]，價值是 w [ i ] w[i] w[i]，現在需要選擇一些物品放入背包，并且總容量不能超過背包容量，求能夠達到的物品的最大總價值，

??以上就是 0/1 背包問題的完整描述，之所以叫 0/1 背包，是因為每種物品只有一個，可以選擇放入背包或者不放，而 0 代表不放，1 代表放，
??第一步：設計狀態；
??狀態 ( i , j ) (i, j) (i,j) 表示前 i i i 個物品恰好放入容量為 j j j 的背包 ( i ∈ [ 0 , n ] , j ∈ [ 0 , m ] ) (i \in [0, n], j \in [0, m]) (i∈[0,n],j∈[0,m])；
??令 d p [ i ] [ j ] dp[i][j] dp[i][j] 表示狀態 ( i , j ) (i, j) (i,j) 下該背包得到的最大價值，即前 i i i 個物品恰好放入容量為 j j j 的背包所得到的最大總價值；
??第二步：列出狀態轉移方程； d p [ i ] [ j ] = m a x ( d p [ i ? 1 ] [ j ] , d p [ i ? 1 ] [ j ? c [ i ] ] + w [ i ] ) dp[i][j] = max(dp[i-1][j], dp[i-1][j - c[i]] + w[i]) dp[i][j]=max(dp[i?1][j],dp[i?1][j?c[i]]+w[i]) 因為每個物品要么放，要么不放，所以只需要考慮第 i i i 個物品 放 或 不放 的情況：
??1）不放：如果 “第 i i i 個物品不放入容量為 j j j 的背包”，那么問題轉化成求 “前 i ? 1 i-1 i?1 個物品放入容量為 j j j 的背包” 的問題；由于不放，所以最大價值就等于 “前 i ? 1 i-1 i?1 個物品放入容量為 j j j 的背包” 的最大價值，即 d p [ i ? 1 ] [ j ] dp[i-1][j] dp[i?1][j]；
??2）放：如果 “第 i i i 個物品放入容量為 j j j 的背包”，那么問題轉化成求 “前 i ? 1 i-1 i?1 個物品放入容量為 j ? c [ i ] j-c[i] j?c[i] 的背包” 的問題；那么此時最大價值就等于 “前 i ? 1 i-1 i?1 個物品放入容量為 j ? c [ i ] j-c[i] j?c[i] 的背包” 的最大價值 加上放入第 i i i 個物品的價值，即 d p [ i ? 1 ] [ j ? c [ i ] ] + w [ i ] dp[i-1][j - c[i]] + w[i] dp[i?1][j?c[i]]+w[i]；
??將以上兩種情況取大者，就是我們所求的 “前 i i i 個物品恰好放入容量為 j j j 的背包” 的最大價值了，
??我們發現，當狀態在進行轉移的時候， ( i , j ) (i, j) (i,j) 不是來自 ( i ? 1 , j ) (i-1, j) (i?1,j)，就是來自 ( i ? 1 , j ? c [ i ] ) (i-1, j - c[i]) (i?1,j?c[i])，所以必然有一個初始狀態，而這個初始狀態就是 ( 0 , 0 ) (0, 0) (0,0)，含義是 “前 0 個物品放入一個背包容量為 0 的背包”，這個狀態下的最大價值為 0，即 d p [ 0 ] [ 0 ] = 0 dp[0][0] = 0 dp[0][0]=0；
??那么我們再來考慮， ( 0 , 3 ) (0, 3) (0,3) 是什么意思呢？它代表的是 “前 0 個物品恰好放入一個背包容量為 3 的背包”，明顯這種情況是不存在的，因為 0 個物品的價值肯定是 0，所以這種狀態被稱為非法狀態，非法狀態是無法進行狀態轉移的，于是我們可以通過初始狀態和非法狀態進所有狀態進行初始化，
?? d p [ 0 ] [ i ] = { 0 i = 0 i n f i > 0 dp[0][i] = \begin{cases} 0 & i = 0\\ inf & i > 0\end{cases} dp[0][i]={0inf?i=0i>0?
??其中 i n f inf inf 在程式實作時，我們可以設定一個非常小的數，比如 ? 1000000000 -1000000000 ?1000000000，只要保證無論如何狀態轉移它都不能成為最優解的候選狀態，為了加深狀態轉移的概念，來看圖二-5-1 的一個例子，每個格子代表一個狀態， ( 0 , 0 ) (0,0) (0,0) 代表初始狀態，藍色的格子代表已經求得的狀態，灰色的格子代表非法狀態，紅色的格子代表當前正在進行轉移的狀態，圖中的第 i i i 行代表了前 i i i 個物品對應容量的最優值，第 4 個物品的容量為 2，價值為 8，則有狀態轉移如下： d p [ 4 ] [ 4 ] = m a x ( d p [ 4 ? 1 ] [ 4 ] , d p [ 4 ? 1 ] [ 4 ? 2 ] + 8 ) = m a x ( d p [ 3 ] [ 4 ] , d p [ 3 ] [ 2 ] + 8 ) \begin{aligned} dp[4][4] &= max( dp[4-1][4], dp[4-1][4 - 2] + 8) \\ &= max( dp[3][4], dp[3][2] + 8) \end{aligned} dp[4][4]?=max(dp[4?1][4],dp[4?1][4?2]+8)=max(dp[3][4],dp[3][2]+8)?

??有關 0/1 背包的更多內容，可以參考：夜深人靜寫演算法（十四）- 0/1 背包，

2、完全背包

??有 n ( n ≤ 100 ) n(n \le 100) n(n≤100) 種物品和一個容量為 m ( m ≤ 10000 ) m(m \le 10000) m(m≤10000) 的背包，第 i i i 種物品的容量是 c [ i ] c[i] c[i]，價值是 w [ i ] w[i] w[i]，現在需要選擇一些物品放入背包，每種物品可以無限選擇，并且總容量不能超過背包容量，求能夠達到的物品的最大總價值，

??以上就是完全背包問題的完整描述，和 0/1 背包的區別就是每種物品可以無限選取，即文中紅色字體標注的內容；
??第一步：設計狀態；
??狀態 ( i , j ) (i, j) (i,j) 表示前 i i i 種物品恰好放入容量為 j j j 的背包 ( i ∈ [ 0 , n ] , j ∈ [ 0 , m ] ) (i \in [0, n], j \in [0, m]) (i∈[0,n],j∈[0,m])；
??令 d p [ i ] [ j ] dp[i][j] dp[i][j] 表示狀態 ( i , j ) (i, j) (i,j) 下該背包得到的最大價值，即前 i i i 種物品（每種物品可以選擇無限件）恰好放入容量為 j j j 的背包所得到的最大總價值；

??第二步：列出狀態轉移方程； d p [ i ] [ j ] = m a x ( d p [ i ? 1 ] [ j ? c [ i ] ? k ] + w [ i ] ? k ) dp[i][j] = max(dp[i-1][j - c[i]*k] + w[i]*k) dp[i][j]=max(dp[i?1][j?c[i]?k]+w[i]?k) ( 0 ≤ k ≤ j c [ i ] ) (0 \le k \le \frac {j} {c[i]}) (0≤k≤c[i]j?)

• 因為每種物品有無限種可放置，將它歸類為以下兩種情況：
  ??1）不放：如果 “第 i i i 種物品不放入容量為 j j j 的背包”，那么問題轉化成求 “前 i ? 1 i-1 i?1 種物品放入容量為 j j j 的背包” 的問題；由于不放，所以最大價值就等于 “前 i ? 1 i-1 i?1 種物品放入容量為 j j j 的背包” 的最大價值，對應狀態轉移方程中 k = 0 k = 0 k=0 的情況， 即 d p [ i ? 1 ] [ j ] dp[i-1][j] dp[i?1][j]；
  ??2）放 k 個：如果 “第 i i i 種物品放入容量為 j j j 的背包”，那么問題轉化成求 “前 i ? 1 i-1 i?1 種物品放入容量為 j ? c [ i ] ? k j-c[i]*k j?c[i]?k 的背包” 的問題；那么此時最大價值就等于 “前 i ? 1 i-1 i?1 種物品放入容量為 j ? c [ i ] ? k j-c[i]*k j?c[i]?k 的背包” 的最大價值 加上放入 k k k 個第 i i i 種物品的價值，即 d p [ i ? 1 ] [ j ? c [ i ] ? k ] + w [ i ] ? k dp[i-1][j - c[i]*k] + w[i]*k dp[i?1][j?c[i]?k]+w[i]?k；
  ??列舉所有滿足條件的 k k k 就是我們所求的 “前 i i i 種物品恰好放入容量為 j j j 的背包” 的最大價值了，注意：由于每件物品都可以無限選擇，所以這里描述的時候都是用的 “種” 作為單位，即代表不同種類的物品，

??對于 n n n 種物品放入一個容量為 m m m 的背包，狀態數為 O ( n m ) O(nm) O(nm)，每次狀態轉移的消耗為 O ( k ) O(k) O(k)，所以整個狀態轉移的程序時間復雜度是大于 O ( n m ) O(nm) O(nm) 的，那么實際是多少呢？考慮最壞情況下，即 c [ i ] = 1 c[i] = 1 c[i]=1 時，那么要計算的 d p [ i ] [ j ] dp[i][j] dp[i][j] 的轉移數為 j j j，總的狀態轉移次數就是 m ( m + 1 ) 2 \frac {m(m + 1)} {2} 2m(m+1)?，所以整個演算法的時間復雜度是 O ( n m 2 ) O(nm^2) O(nm2) 的，也就是說狀態轉移均攤時間復雜度是 O ( m ) O(m) O(m) 的，

??我們把狀態轉移方程進行展開后得到如下的 k + 1 k+1 k+1 個式子：
d p [ i ] [ j ] = m a x { d p [ i ? 1 ] [ j ] ( 1 ) d p [ i ? 1 ] [ j ? c [ i ] ] + w [ i ] ( 2 ) d p [ i ? 1 ] [ j ? c [ i ] ? 2 ] + w [ i ] ? 2 ( 3 ) . . . d p [ i ? 1 ] [ j ? c [ i ] ? k ] + w [ i ] ? k ( k + 1 ) dp[i][j] = max \begin{cases} dp[i-1][j] & (1)\\ dp[i-1][j - c[i]] + w[i] & (2)\\ dp[i-1][j - c[i]*2] + w[i]*2 & (3)\\ ... \\ dp[i-1][j - c[i]*k] + w[i] *k & (k+1) \end{cases} dp[i][j]=max????????????????dp[i?1][j]dp[i?1][j?c[i]]+w[i]dp[i?1][j?c[i]?2]+w[i]?2...dp[i?1][j?c[i]?k]+w[i]?k?(1)(2)(3)(k+1)?
??利用待定系數法，用 j ? c [ i ] j-c[i] j?c[i] 代替上式的 j j j 得到如下式子：
d p [ i ] [ j ? c [ i ] ] = m a x { d p [ i ? 1 ] [ j ? c [ i ] ] ( 1 ) d p [ i ? 1 ] [ j ? c [ i ] ? 2 ] + w [ i ] ( 2 ) d p [ i ? 1 ] [ j ? c [ i ] ? 3 ] + w [ i ] ? 2 ( 3 ) . . . d p [ i ? 1 ] [ j ? c [ i ] ? k ] + w [ i ] ? ( k ? 1 ) ( k ) dp[i][j-c[i]] = max \begin{cases} dp[i-1][j-c[i]] & (1)\\ dp[i-1][j - c[i]*2] + w[i] & (2)\\ dp[i-1][j - c[i]*3] + w[i]*2 & (3)\\ ... \\ dp[i-1][j - c[i]*k] + w[i] *(k-1) & (k) \end{cases} dp[i][j?c[i]]=max????????????????dp[i?1][j?c[i]]dp[i?1][j?c[i]?2]+w[i]dp[i?1][j?c[i]?3]+w[i]?2...dp[i?1][j?c[i]?k]+w[i]?(k?1)?(1)(2)(3)(k)?
??等式兩邊都加上 w [ i ] w[i] w[i] 得到：
d p [ i ] [ j ? c [ i ] ] + w [ i ] = m a x { d p [ i ? 1 ] [ j ? c [ i ] ] + w [ i ] ( 1 ) d p [ i ? 1 ] [ j ? c [ i ] ? 2 ] + w [ i ] ? 2 ( 2 ) d p [ i ? 1 ] [ j ? c [ i ] ? 3 ] + w [ i ] ? 3 ( 3 ) . . . d p [ i ? 1 ] [ j ? c [ i ] ? k ] + w [ i ] ? k ( k ) dp[i][j-c[i]] + w[i] = max \begin{cases} dp[i-1][j-c[i]] + w[i] & (1)\\ dp[i-1][j - c[i]*2] + w[i]*2 & (2)\\ dp[i-1][j - c[i]*3] + w[i]*3 & (3)\\ ... \\ dp[i-1][j - c[i]*k] + w[i] *k & (k) \end{cases} dp[i][j?c[i]]+w[i]=max????????????????dp[i?1][j?c[i]]+w[i]dp[i?1][j?c[i]?2]+w[i]?2dp[i?1][j?c[i]?3]+w[i]?3...dp[i?1][j?c[i]?k]+w[i]?k?(1)(2)(3)(k)?
??于是我們發現，這里的 ( 1 ) . . . ( k ) (1)...(k) (1)...(k) 式子等價于最開始的狀態轉移方程中的 ( 2 ) . . . ( k + 1 ) (2) ... (k+1) (2)...(k+1) 式，所以原狀態轉移方程可以簡化為： d p [ i ] [ j ] = m a x ( d p [ i ? 1 ] [ j ] , d p [ i ] [ j ? c [ i ] ] + w [ i ] ) dp[i][j] = max(dp[i-1][j], dp[i][j-c[i]] + w[i]) dp[i][j]=max(dp[i?1][j],dp[i][j?c[i]]+w[i])
??這樣就把原本均攤時間復雜度為 O ( m ) O(m) O(m) 的狀態轉移優化到了 O ( 1 ) O(1) O(1)，
??那么我們來理解一下這個狀態轉移方程的含義：對于第 i i i 種物品，其實只有兩種選擇：一個都不放、至少放一個；一個都不放 就是 “前 i ? 1 i-1 i?1 種物品放滿一個容量為 j j j 的背包” 的情況，即 d p [ i ? 1 ] [ j ] dp[i-1][j] dp[i?1][j]；至少放一個 的話，我們嘗試在 “前 i i i 種物品放滿一個容量為 j j j 的背包” 里拿掉 1 個物品，即 “前 i i i 種物品放滿一個容量為 j ? c [ i ] j-c[i] j?c[i] 的背包”，這時候的值就是 d p [ i ] [ j ? c [ i ] ] + w [ i ] dp[i][j-c[i]] + w[i] dp[i][j?c[i]]+w[i]，取兩者的大者就是答案了，
??其實這個思路我可以在本文開頭就講，也容易理解，之所以引入優化以及逐步推導的程序，就是想告訴讀者，很多動態規劃的問題是不能套用模板的，從簡單的思路出發，加上一些推導和優化，逐步把復雜的問題循序漸進的求出來，才是解決問題的普遍思路，
??有關完全背包的更多內容，可以參考：夜深人靜寫演算法（十五）- 完全背包，

3、多重背包

??有 n ( n ≤ 100 ) n(n \le 100) n(n≤100) 種物品和一個容量為 m ( m ≤ 10000 ) m(m \le 10000) m(m≤10000) 的背包，第 i i i 種物品的容量是 c [ i ] c[i] c[i]，價值是 w [ i ] w[i] w[i]，現在需要選擇一些物品放入背包，每種物品可以選擇 x [ i ] x[i] x[i] 件，并且總容量不能超過背包容量，求能夠達到的物品的最大總價值，

??以上就是多重背包問題的完整描述，和 0/1 背包、完全背包的區別就是每種物品的選取有物品自己的值域限制，即文中紅色字體標注的內容；
??第一步：設計狀態；
??狀態 ( i , j ) (i, j) (i,j) 表示前 i i i 種物品恰好放入容量為 j j j 的背包 ( i ∈ [ 0 , n ] , j ∈ [ 0 , m ] ) (i \in [0, n], j \in [0, m]) (i∈[0,n],j∈[0,m])；
??令 d p [ i ] [ j ] dp[i][j] dp[i][j] 表示狀態 ( i , j ) (i, j) (i,j) 下該背包得到的最大價值，即前 i i i 種物品（每種物品可以選擇 x [ i ] x[i] x[i] 件）恰好放入容量為 j j j 的背包所得到的最大總價值；

??第二步：列出狀態轉移方程； d p [ i ] [ j ] = m a x ( d p [ i ? 1 ] [ j ? c [ i ] ? k ] + w [ i ] ? k ) ( 0 ≤ k ≤ x [ i ] ) dp[i][j] = max(dp[i-1][j - c[i]*k] + w[i]*k) \\ (0 \le k \le x[i]) dp[i][j]=max(dp[i?1][j?c[i]?k]+w[i]?k)(0≤k≤x[i]) 因為每種物品有 x [ i ] x[i] x[i] 種可放置，將它歸類為以下兩種情況：
??1）不放：如果 “第 i i i 種物品不放入容量為 j j j 的背包”，那么問題轉化成求 “前 i ? 1 i-1 i?1 種物品放入容量為 j j j 的背包” 的問題；由于不放，所以最大價值就等于 “前 i ? 1 i-1 i?1 種物品放入容量為 j j j 的背包” 的最大價值，對應狀態轉移方程中 k = 0 k = 0 k=0 的情況， 即 d p [ i ? 1 ] [ j ] dp[i-1][j] dp[i?1][j]；
??2）放 k 個：如果 “第 i i i 種物品放入容量為 j j j 的背包”，那么問題轉化成求 “前 i ? 1 i-1 i?1 種物品放入容量為 j ? c [ i ] ? k j-c[i]*k j?c[i]?k 的背包” 的問題；那么此時最大價值就等于 “前 i ? 1 i-1 i?1 種物品放入容量為 j ? c [ i ] ? k j-c[i]*k j?c[i]?k 的背包” 的最大價值 加上放入 k k k 個第 i i i 種物品的價值，即 d p [ i ? 1 ] [ j ? c [ i ] ? k ] + w [ i ] ? k dp[i-1][j - c[i]*k] + w[i]*k dp[i?1][j?c[i]?k]+w[i]?k；
??列舉所有滿足條件的 k k k 就是我們所求的 “前 i i i 種物品恰好放入容量為 j j j 的背包” 的最大價值了，
??多重背包問題是背包問題的一般情況，每種物品有自己的值域限制，如果從狀態轉移方程出發，我們可以把三種背包問題進行歸納統一，得到一個統一的狀態轉移方程如下： d p [ i ] [ j ] = m a x ( d p [ i ? 1 ] [ j ? c [ i ] ? k ] + w [ i ] ? k ) dp[i][j] = max(dp[i-1][j - c[i]*k] + w[i]*k) dp[i][j]=max(dp[i?1][j?c[i]?k]+w[i]?k)??對于 0/1 背包問題， k k k 的取值為 0 , 1 0,1 0,1；
??對于完全背包問題， k k k 的取值為 0 , 1 , 2 , 3 , . . . , ? j c [ i ] ? 0, 1, 2, 3, ..., \lfloor \frac j {c[i]} \rfloor 0,1,2,3,...,?c[i]j??；
??對于多重背包問題， k k k 的取值為 0 , 1 , 2 , 3 , . . . , x [ i ] 0, 1, 2, 3, ..., x[i] 0,1,2,3,...,x[i]；
??對于 n n n 種物品放入一個容量為 m m m 的背包，狀態數為 O ( n m ) O(nm) O(nm)，每次狀態轉移的消耗為 O ( x [ i ] ) O(x[i]) O(x[i])，所以整個狀態轉移的程序時間復雜度是大于 O ( n m ) O(nm) O(nm) 的，那么實際是多少呢？
??考慮最壞情況下，即 x [ i ] = m x[i] = m x[i]=m 時，那么要計算的 d p [ i ] [ j ] dp[i][j] dp[i][j] 的轉移數為 j j j，總的狀態轉移次數就是 m ( m + 1 ) 2 \frac {m(m + 1)} {2} 2m(m+1)?，所以整個演算法的時間復雜度是 O ( n m 2 ) O(nm^2) O(nm2) 的，也就是說狀態轉移均攤時間復雜度是 O ( m ) O(m) O(m) 的，
??一個容易想到的優化是：我們可以將每種物品拆成 x [ i ] x[i] x[i] 個，這樣變成了 ∑ i = 1 n x [ i ] \sum_{i=1}^n x[i] ∑i=1n?x[i] 個物品的 0/1 背包問題，我們知道 0/1 背包問題優化完以后，空間復雜度只和容量有關，即 O ( m ) O(m) O(m)，
??所以多重背包問題的空間復雜度至少是可以優化到 O ( m ) O(m) O(m) 的，
??然而， 如果這樣拆分，時間復雜度還是沒有變化，但是給我們提供了一個思路，就是每種物品是可以拆分的，假設有 x [ i ] x[i] x[i] 個物品，我們可以按照 2 的冪進行拆分，把它拆分成： 1 , 2 , 4 , . . . , 2 k ? 1 , x [ i ] ? 2 k + 1 1, 2, 4, ..., 2^{k-1}, x[i] - 2^{k} + 1 1,2,4,...,2k?1,x[i]?2k+1
??其中 k k k 是最大的滿足 x [ i ] ? 2 k + 1 ≥ 0 x[i] - 2^{k} + 1 \ge 0 x[i]?2k+1≥0 的非負整數，
??這樣，1 到 x [ i ] x[i] x[i] 之間的所有整數都能通過以上 k + 1 k+1 k+1 個數字組合出來，所以只要拆成以上 k + 1 k+1 k+1 個物品，所有取 k ( 0 ≤ k ≤ x [ i ] ) k (0 \le k \le x[i]) k(0≤k≤x[i]) 個物品的情況都能被考慮進來，
??舉例說明，當 x [ i ] = 14 x[i] = 14 x[i]=14 時，可以拆分成 1,2,4,7 個物品，那么當我們要取 13 個這類物品的時候，相當于選擇 2、4、7，容量分別為 c [ i ] ? 2 , c [ i ] ? 4 , c [ i ] ? 7 c[i]*2, c[i]*4, c[i]* 7 c[i]?2,c[i]?4,c[i]?7, 價值分別為 w [ i ] ? 2 , w [ i ] ? 4 , w [ i ] ? 7 w[i]*2, w[i]*4, w[i]* 7 w[i]?2,w[i]?4,w[i]?7，
??通過這種拆分方式， x [ i ] x[i] x[i] 最多被拆分成 l o g 2 x [ i ] log_2 {x[i]} log2?x[i] 個物品，然后再用 0/1 背包求解，得到了一個時間復雜度為 O ( m ∑ i = 1 n l o g 2 x [ i ] ) O(m\sum_{i=1}^{n}log_2{x[i]}) O(m∑i=1n?log2?x[i]) 的演算法，
??有關多重背包的更多內容，可以參考：夜深人靜寫演算法（十六）- 多重背包，

4、分組背包

??有 n ( n ≤ 1000 ) n(n \le 1000) n(n≤1000) 個物品和一個容量為 m ( m ≤ 1000 ) m(m \le 1000) m(m≤1000) 的背包，這些物品被分成若干組，第 i i i 個物品屬于 g [ i ] g[i] g[i] 組，容量是 c [ i ] c[i] c[i]，價值是 w [ i ] w[i] w[i]，現在需要選擇一些物品放入背包，并且每組最多放一個物品，總容量不能超過背包容量，求能夠達到的物品的最大總價值，

??以上就是分組背包問題的完整描述，和其它背包問題的區別就是每個物品多了一個組號，并且相同組內，最多只能選擇一個物品放入背包；因為只有一個物品，所以讀者可以暫時忘掉 完全背包 和 多重背包 的概念，在往下看之前，先回憶一下 0/1 背包的狀態轉移方程，

??第一步：預處理；
??首先把每個物品按照組號 g [ i ] g[i] g[i] 從小到大排序，假設總共有 t t t 組，則將 g [ i ] g[i] g[i] 按順序離散到 [ 1 , t ] [1,t] [1,t] 的正整數，這樣做的目的是為了將 g [ i ] g[i] g[i] 作為下標映射到狀態陣列中；

??第二步：設計狀態；
??狀態 ( k , j ) (k, j) (k,j) 表示前 k k k 組物品恰好放入容量為 j j j 的背包 ( k ∈ [ 0 , t ] , j ∈ [ 0 , m ] ) (k \in [0, t], j \in [0, m]) (k∈[0,t],j∈[0,m])；令 d p [ k ] [ j ] dp[k][j] dp[k][j] 表示狀態 ( k , j ) (k, j) (k,j) 下該背包得到的最大價值，即前 k k k 組物品（每組物品至多選一件）恰好放入容量為 j j j 的背包所得到的最大總價值；

??第三步：列出狀態轉移方程： d p [ k ] [ j ] = m a x ( d p [ k ? 1 ] [ j ] , d p [ k ? 1 ] [ j ? c [ i ] ] + w [ i ] ) dp[k][j] = max(dp[k-1][j], dp[k-1][j - c[i]] + w[i]) dp[k][j]=max(dp[k?1][j],dp[k?1][j?c[i]]+w[i]) k = g [ i ] k = g[i] k=g[i]因為每個物品有只有兩種情況：
??1）不放：如果 “第 i i i 個物品（屬于第 k k k 組）不放入容量為 j j j 的背包”，那么問題轉化成求 “前 k ? 1 k-1 k?1 組物品放入容量為 j j j 的背包” 的問題；由于不放，所以最大價值就等于 “前 k ? 1 k-1 k?1 組物品放入容量為 j j j 的背包” 的最大價值，對應狀態轉移方程中的 d p [ k ? 1 ] [ j ] dp[k-1][j] dp[k?1][j]；
??2）放：如果 “第 i i i 個物品（屬于第 k k k 組）放入容量為 j j j 的背包”，那么問題轉化成求 “前 k ? 1 k-1 k?1 組物品放入容量為 j ? c [ i ] j-c[i] j?c[i] 的背包” 的問題；那么此時最大價值就等于 “前 k ? 1 k-1 k?1 組物品放入容量為 j ? c [ i ] j-c[i] j?c[i] 的背包” 的最大價值 加上放入第 i i i 個物品的價值，即 d p [ k ? 1 ] [ j ? c [ i ] ] + w [ i ] dp[k-1][j - c[i]] + w[i]

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

標籤：其他

上一篇：推薦 7 個 yyds 的開源專案

下一篇：JSON檔案多個根