在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ì)心一點(diǎn)你會發(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ù)組降維成點(diǎn)罚勾。
如果我們把問題泛化毅人，不再是固定的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ù)組缔俄，就實(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ù)來計(jì)算可以湊成總金額的硬幣組合數(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)你運(yùn)行之后走敌，卻發(fā)現(xiàn)這個代碼并不正確，得到的結(jié)果比預(yù)期的大逗噩。究其原因掉丽，該代碼計(jì)算的結(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ù)项炼。說的更加直白一點(diǎn)，那就是用前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。
因?yàn)檫@是個組合問題墨坚，我們不關(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), 這是因?yàn)榈谝涣惺怯矌艦?的基本情況盗尸。
此時，交換這里面的循環(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ù)組降維成點(diǎn)。這里問題能不能也試著降低一個維度亏拉，只用一個數(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)能換嗎？
顯然不能栋猖，因?yà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
