在LeetCode上有兩道題目非常類似，分別是
如果我們把每次可走步數(shù)/零錢面額限制為[1,2], 把樓梯高度/總金額限制為3. 那么這兩道題目就可以抽象成"給定[1,2], 求組合成3的組合數(shù)和排列數(shù)"。
接下來引出本文的核心兩段代碼，雖然是Cpp寫的，但是都是最基本的語法，對于可能看不懂的地方，我加了注釋。
class Solution1 {
public:
int change(int amount, vector<int>& coins) {
int dp[amount+1];
memset(dp, 0, sizeof(dp)); //初始化數(shù)組為0
dp[0] = 1;
for (int j = 1; j <= amount; j++){ //枚舉金額
for (int coin : coins){ //枚舉硬幣
if (j < coin) continue; // coin不能大于amount
dp[j] += dp[j-coin];
}
}
return dp[amount];
}
};
class Solution2 {
public:
int change(int amount, vector<int>& coins) {
int dp[amount+1];
memset(dp, 0, sizeof(dp)); //初始化數(shù)組為0
dp[0] = 1;
for (int coin : coins){ //枚舉硬幣
for (int j = 1; j <= amount; j++){ //枚舉金額
if (j < coin) continue; // coin不能大于amount
dp[j] += dp[j-coin];
}
}
return dp[amount];
}
};
如果不仔細(xì)看，你會覺得這兩個Solution似乎是一模一樣的代碼，但細(xì)心一點你會發(fā)現(xiàn)他們在嵌套循環(huán)上存在了差異。這個差異使得一個求解結(jié)果是排列數(shù)，一個求解結(jié)果是組合數(shù)。
因此在不看后面的分析之前，你能分辨出哪個Solution是得到排列，哪個Solution是得到組合嗎？
在揭曉答案之前，讓我們先分別用DP的方法解決爬樓梯和零錢兌換II的問題。每個解題步驟都按照DP三部曲，a.定義子問題，b. 定義狀態(tài)數(shù)組，c. 定義狀態(tài)轉(zhuǎn)移方程。
70. 爬樓梯
問題描述如下:
假設(shè)你正在爬樓梯。需要 n 階你才能到達(dá)樓頂。
每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂呢？
這道題目子問題是，problem(i) = sub(i-1) + sub(i-2), 即求解第i階樓梯等于求解第i-1階樓梯和第i-2階樓梯之和。
狀態(tài)數(shù)組是 DP[i], 狀態(tài)轉(zhuǎn)移方程是DP[i] = DP[i-1] = DP[i-2]
那么代碼也就可以寫出來了。
class Solution {
public:
int climbStairs(int n) {
int DP[n+1];
memset(DP, 0, sizeof(DP));
DP[0] = 1;
DP[1] = 1;
for (int i = 2; i <= n; i++){
DP[i] = DP[i-1] + DP[i-2] ;
}
return DP[n];
}
};
由于每次我們只關(guān)注DP[i-1]和DP[i-2]，所以代碼中能把數(shù)組替換成2個變量，降低空間復(fù)雜度，可以認(rèn)為是將一維數(shù)組降維成點。
如果我們把問題泛化，不再是固定的1，2，而是任意給定臺階數(shù)，例如1,2,5呢？
我們只需要修改我們的DP方程DP[i] = DP[i-1] + DP[i-2] + DP[i-5], 也就是DP[i] = DP[i] + DP[i-j] ,j =1,2,5
在原來的基礎(chǔ)上，我們的代碼可以做這樣子修改
class Solution {
public:
int climbStairs(int n) {
int DP[n+1];
memset(DP, 0, sizeof(DP));
DP[0] = 1;
int steps[2] = {1,2};
for (int i = 1; i <= n; i++){
for (int j = 0; j < 2; j++){
int step = steps[j];
if ( i < step ) continue;// 臺階少于跨越的步數(shù)
DP[i] = DP[i] + DP[i-step];
}
}
return DP[n];
}
};
后續(xù)修改steps數(shù)組，就實現(xiàn)了原來問題的泛化。
那么這個代碼是不是看起來很眼熟呢？我們能不能交換內(nèi)外的循環(huán)呢？也就是下面的代碼
for (int j = 0; j < 2; j++){
int step = steps[j];
for (int i = 1; i <= n; i++){
if ( i < step ) continue;// 臺階少于跨越的步數(shù)
DP[i] = DP[i] + DP[i-step];
}
}
大家可以嘗試思考下這個問題，嵌套循環(huán)是否能夠調(diào)換，調(diào)換之后的DP方程的含義有沒有改變？
零錢兌換II
問題描述如下:
給定不同面額的硬幣和一個總金額。寫出函數(shù)來計算可以湊成總金額的硬幣組合數(shù)。假設(shè)每一種面額的硬幣有無限個。
定義子問題: problem(i) = sum( problem(i-j) ), j =1,2,5. 含義為湊成總金額i的硬幣組合數(shù)等于湊成總金額硬幣i-1, i-2, i-5,...的子問題之和。
我們發(fā)現(xiàn)這個子問題定義居然和我們之前泛化的爬樓梯問題居然是一樣的，那后面的狀態(tài)數(shù)組和狀態(tài)轉(zhuǎn)移方程也是一樣的，所以當(dāng)前問題的代碼可以在之前的泛化爬樓梯問題中進(jìn)行修改而得。
class Solution {
public:
int change(int amount, vector<int>& coins) {
int dp[amount+1];
memset(dp, 0, sizeof(dp)); //初始化數(shù)組為0
dp[0] = 1;
for (int j = 1; j <= amount; j++){ //枚舉金額
for (int i = 0; i < coins.size(): i++){
int coin = coins[i]; //枚舉硬幣
if (j < coin) continue; // coin不能大于amount
dp[j] += dp[j-coin];
}
}
return dp[amount];
}
};
這就是我們之前的Solution1代碼。
但是當(dāng)你運行之后，卻發(fā)現(xiàn)這個代碼并不正確，得到的結(jié)果比預(yù)期的大。究其原因，該代碼計算的結(jié)果是排列數(shù)，而不是組合數(shù)，也就是代碼會把1,2和2,1當(dāng)做兩種情況。但更加根本的原因是我們子問題定義出現(xiàn)了錯誤。
正確的子問題定義應(yīng)該是，problem(k,i) = problem(k-1, i) + problem(k, i-k)
即前k個硬幣湊齊金額i的組合數(shù)等于前k-1個硬幣湊齊金額i的組合數(shù)加上在原來i-k的基礎(chǔ)上使用硬幣的組合數(shù)。說的更加直白一點，那就是用前k的硬幣湊齊金額i，要分為兩種情況開率，一種是沒有用前k-1個硬幣就湊齊了，一種是前面已經(jīng)湊到了i-k，現(xiàn)在就差第k個硬幣了。
狀態(tài)數(shù)組就是DP[k][i], 即前k個硬幣湊齊金額i的組合數(shù)。
這里不再是一維數(shù)組，而是二維數(shù)組。第一個維度用于記錄當(dāng)前組合有沒有用到硬幣k，第二個維度記錄現(xiàn)在湊的金額是多少？如果沒有第一個維度信息，當(dāng)我們湊到金額i的時候，我們不知道之前有沒有用到硬幣k。
因為這是個組合問題，我們不關(guān)心硬幣使用的順序，而是硬幣有沒有被用到。是否使用第k個硬幣受到之前情況的影響。
狀態(tài)轉(zhuǎn)移方程如下
if 金額數(shù)大于硬幣
DP[k][i] = DP[k-1][i] + DP[k][i-k]
else
DP[k][i] = DP[k-1][i]
因此正確代碼如下:
class Solution {
public:
int change(int amount, vector<int>& coins) {
int K = coins.size() + 1;
int I = amount + 1;
int DP[K][I];
//初始化數(shù)組
for (int k = 0; k < K; k++){
for (int i = 0; i < I; i++){
DP[k][i] = 0;
}
}
//初始化基本狀態(tài)
for (int k = 0; k < coins.size() + 1; k++){
DP[k][0] = 1;
}
for (int k = 1; k <= coins.size() ; k++){
for (int i = 1; i <= amount; i++){
if ( i >= coins[k-1]) {
DP[k][i] = DP[k][i-coins[k-1]] + DP[k-1][i];
} else{
DP[k][i] = DP[k-1][k];
}
}
}
return DP[coins.size()][amount];
}
};
我們初始化的數(shù)組大小為coins.size()+1* (amount+1), 這是因為第一列是硬幣為0的基本情況。
此時，交換這里面的循環(huán)不會影響最終的結(jié)果。也就是
for (int i = 1; i <= amount; i++){
for (int k = 1; k <= coins.size() ; k++){
if ( i >= coins[k-1]) {
DP[k][i] = DP[k][i-coins[k-1]] + DP[k-1][i];
} else{
DP[k][i] = DP[k-1][k];
}
}
}
之前爬樓梯問題中，我們將一維數(shù)組降維成點。這里問題能不能也試著降低一個維度，只用一個數(shù)組進(jìn)行表示呢？
這個時候，我們就需要重新定義我們的子問題了。
此時的子問題是，對于硬幣從0到k，我們必須使用第k個硬幣的時候，當(dāng)前金額的組合數(shù)。
因此狀態(tài)數(shù)組DP[i]表示的是對于第k個硬幣能湊的組合數(shù)
狀態(tài)轉(zhuǎn)移方程如下
DP[[i] = DP[i] + DP[i-k]
于是得到我們開頭的第二個Solution。
class Solution {
public:
int change(int amount, vector<int>& coins) {
int dp[amount+1];
memset(dp, 0, sizeof(dp)); //初始化數(shù)組為0
dp[0] = 1;
for (int coin : coins){ //枚舉硬幣
for (int i = 1; i <= amount; i++){ //枚舉金額
if (i < coin) continue; // coin不能大于amount
dp[i] += dp[i-coin];
}
}
return dp[amount];
}
};
好了，繼續(xù)之前的問題，這里的內(nèi)外循環(huán)能換嗎？
顯然不能，因為我們這里定義的子問題是，必須選擇第k個硬幣時，湊成金額i的方案。如果交換了，我們的子問題就變了，那就是對于金額i, 我們選擇硬幣的方案。
同樣的，我們回答之前爬樓梯的留下的問題，原循環(huán)結(jié)構(gòu)對應(yīng)的子問題是，對于樓梯數(shù)i, 我們的爬樓梯方案。第二種循環(huán)結(jié)構(gòu)則是，固定爬樓梯的順序，我們爬樓梯的方案。也就是第一種循環(huán)下，對于樓梯3，你可以先2再1，或者先1再2，但是對于第二種循環(huán)
參考資料
- https://leetcode-cn.com/problems/coin-change-2/solution/518-ling-qian-dui-huan-ii-you-hua-dong-tai-gui-hua/
- 背包問題9講:https://raw.githubusercontent.com/tianyicui/pack/master/V2.pdf
- labuladong的算法小抄: https://labuladong.gitbook.io/algo/di-ling-zhang-bi-du-xi-lie/xue-xi-shu-ju-jie-gou-he-suan-fa-de-gao-xiao-fang-fa
