今天又是補打卡的一天，開沖?。?！
今日任務(wù)：
- 70.爬樓梯（進階）
- 322.零錢兌換
- 279.完全平方數(shù)
題目一：爬樓梯（進階）
這道題之前做過一次，但是可以采用完全背包的問題來分析一遍。
卡瑪網(wǎng)題目：【57.爬樓梯】
這個題目其實是更難了一點，因為前面的題目都是每次要不爬1階樓梯，要不爬2階樓梯，現(xiàn)在相當于是任選，而且還是可以重復(fù)利用的，因此此問題可以轉(zhuǎn)化為排列方式的完全背包問題。
按照遞歸五部曲：
（1）定義dp數(shù)組及其含義：
dp[j]表示爬到j(luò)階樓梯，有dp[j]種方法。
（2）確定遞推公式：
因為這個是方法類的，所以遞推公式通常為：dp[j] = dp[j-nums[i]]，此題種的nums[i]對應(yīng)的就是1、2、3、4這種，因此可以轉(zhuǎn)換為dp[j] = dp[j-i]；
（3）dp數(shù)組初始化：
dp[0] = 1；如果初始化dp[0] = 0，那后面的全部都是0;
（4）確定遍歷順序：
因為這個是排列的完全背包問題；
完全背包問題相對于01背包問題，其實是第二層變成了從左到右遍歷，然后因為又是排列的問題，所以是先背包后物品。
（5）打印dp數(shù)組：
一般用來判斷和自己想的是否一致
易錯點：在遞推公式前面需要判斷一下才能放，這個是完全背包排列問題中非常重要的東西
#include <iostream>
#include <vector>
using namespace std;
int main(){
int m = 0, n = 0;
while(cin >> n >> m){
vector<int> dp(n+1);
dp[0] = 1;
for(int i = 1; i<=n; i++){
for(int j = 0; j<=m; j++){
if(i>=j) dp[i] += dp[i-j];
}
}
cout << dp[n];
}
return 0;
}
題目二：零錢兌換
Leetcode題目：【322.零錢兌換】
從題目中大致可以看出來是完全背包類的題目，按照遞歸五部曲：
1、定義dp數(shù)組的含義：dp[j]表示裝滿j，最少的硬幣數(shù)目為dp[j]；
2、確定遞推公式：
dp[j] = min(dp[j-coins[i]] + 1, dp[j]);
3、初始化：
dp[0] = 0;
因為取得都是最小，故為了不影響式子的值，所以需要初始化最大值；
4、遍歷順序：
按照完全背包的問題，可以是組合也可以是排列問題；
5、打印dp數(shù)組
此處需要注意在遞推公式的判斷條件，因為有可能dp[i]某些并不會初始化。
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
vector<int> dp(amount + 1, INT_MAX);
dp[0] = 0;
for(int i = 0; i<coins.size(); i++){
for(int j = coins[i]; j<=amount; j++){
//dp[j] = min(dp[j], dp[j-coins[i]] + 1);
if (dp[j - coins[i]] != INT_MAX){
dp[j] = min(dp[j], dp[j-coins[i]] + 1);
}
}
}
if (dp[amount] == INT_MAX) return -1;
for(int i = 0; i<=amount; i++){
cout << dp[i] << " ";
}
return dp[amount];
}
};
題目三：279.完全平方數(shù)
Leetcode題目：【279.完全平方數(shù)】
這個題跟上面的題目基本一樣，只不過此題需要我們自己去創(chuàng)造物品，物品就是i*i，因為完全平方數(shù)中存在1，所以不可能存在不能拼湊的情況。文章來源：http://www.zghlxwxcb.cn/news/detail-843300.html
按照遞歸五部曲：
（1）確定dp數(shù)組含義：dp[j]表示裝滿數(shù)量為j的背包，需要的最少完全平方數(shù)的個數(shù)；
（2）確定遞推公式：
dp[j] = dp[j-nums[i]] + 1 變?yōu)閐p[j] = dp[j-ii] + 1，因為是求最小，所以
dp[j] = min(dp[j], dp[j-ii] + 1);
（3）初始化：dp[0] = 0，同時其他設(shè)置為最大值INT_MAX；
（4）確定遍歷順序：
因為此題是完全背包問題，所以都是正序，因為是組合問題，所以可以先物品再背包；
（5）打印dp數(shù)組；文章來源地址http://www.zghlxwxcb.cn/news/detail-843300.html
class Solution {
public:
int numSquares(int n) {
// 題目就是自己去構(gòu)造物品
vector<int> dp(n+1, INT_MAX);
dp[0] = 0;
for(int i = 1; i*i <= n; i++){
for(int j = i*i; j<=n; j++){
if(dp[j-i*i] != INT_MAX){
dp[j] = min(dp[j], dp[j-i*i] + 1);
}
}
}
return dp[n];
}
};
到了這里，關(guān)于【Day45】代碼隨想錄之動態(tài)規(guī)劃part7—爬樓梯（進階）、零錢兌換、完全平方數(shù)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
