70. 爬樓梯
和377. 組合總和 Ⅳ (opens new window)基本就是一道題了。本題代碼不長，題目也很普通，但稍稍一進階就可以考察完全背包
class Solution {
public:
int climbStairs(int n) {
vector<int> nums = {1,2};
vector<int> dp(n+1,0);
dp[0] = 1;
for(int j = 0; j <=n; j++){
for(int i = 0; i < nums.size(); i++){
if(j >= nums[i]) dp[j] += dp[j - nums[i]];
}
}
return dp[n];
}
};
322. 零錢兌換
動態(tài)規(guī)劃五部曲
1、確定dp[j]的含義
dp[j] 湊成 j 的最少硬幣的個數(shù)
2、確定遞推公式
比如想湊成3，
如果手里有1，那么最小個數(shù)就是dp[2]+1
如果手里有2，那么最小個數(shù)就是dp[1]+1
如果手里有3，那么最小個數(shù)就是dp[0]+1
dp[j] = min（dp[j] , dp[j-nums[i]] + 1）
3、確定初始值
dp[0] = 0
其余值應(yīng)給 INT_MAX。
最終dp[j] == INT_MAX 就返回-1
4、確定遍歷順序
首先這是個完全背包，背包容量從小到大遍歷。其次，{5，5，1} 和{1，5，1}的組合大小都是3，所以兩層for循環(huán)無所謂遍歷順序。
5、驗證
coins = [1, 2, 5], amount = 11
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
vector<int> dp(amount+1,INT_MAX);
dp[0] = 0;
for(int j = 1; j <= amount; ++j){
for(int i = 0; i < coins.size(); ++i){
if(j >= coins[i] && dp[j - coins[i]] != INT_MAX) dp[j] = min(dp[j],dp[j - coins[i]] + 1);
}
}
return dp[amount] == INT_MAX ? -1 : dp[amount];
}
};
279. 完全平方數(shù)
1、dp[j] : 構(gòu)成 j 的完全平方數(shù)的最小數(shù)量
2、dp[j] = min( dp[j] , dp[j - i * i ] + 1)
3、初始化
1 <= n <= 104，所以dp[0]無意義
dp[1] = 1, 其余值給INT_MAX
4、完全背包，求個數(shù)所以不用管兩個for的內(nèi)外
class Solution {
public:
int numSquares(int n) {
vector<int> dp(n+1,INT_MAX);
dp[0] = 0;
dp[1] = 1;
for(int i = 1; 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] ;
}
};
139. 單詞拆分
本題與回溯中：分割回文子串的思路是一樣的，通過分割字符串，得到單詞，再去單詞列表中尋找該單詞是否存在。
回溯寫法：
其中的memory數(shù)組，與之前組合問題中的去重數(shù)組作用一致。本題中通過在對應(yīng)的位置設(shè)置false，來標記該字母后的字符串沒有可分割的方法。例如：
cat sand og，在index = 7的地方設(shè)置false（og），
cats and og，當再一次分割到index = 7的時候，就不再進入for循環(huán)判斷og有無合適的分割方法，而是直接通過memory[7] = false 返回false。
時間復(fù)雜度還是O(2n)，但是比沒有memory數(shù)組的情況好很多。
namespace jj22 {
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
vector<bool> memory(s.size(), 1); // -1 表示初始化狀態(tài)
return backtracking(s, wordSet, 0,memory);
}
bool backtracking(string s,unordered_set<string>& wordSet,int startIndex, vector<bool>& memory) {
if (startIndex >= s.size())return true;
if (!memory[startIndex]) return memory[startIndex];
for (int i = startIndex; i < s.size(); ++i) {
string word = s.substr(startIndex, i - startIndex + 1);
if (wordSet.find(word) != wordSet.end() && backtracking(s, wordSet, i + 1,memory)) {
return true;
}
}
memory[startIndex] = false; // 記錄以startIndex開始的子串是不可以被拆分的
return false;
}
};
void test() {
string s = "catsandog";
vector<string> wordDict = { "cats", "dog", "sand", "and", "cat" };
Solution ss;
bool temp = ss.wordBreak(s, wordDict);
int a = 10;
}
}
背包解法：
首先，本題的物品就是各個單詞，背包容量是字符串長度。由于物品可以重復(fù)拿取，所以是完全背包問題。
五部曲：
1、dp數(shù)組的含義
dp[j] : 長度為j 的字符串能否被單詞列表里的單詞組成
2、遞推公式
當 i < j 時，如果dp[i] = true(即 dp[i] 長度為 i 的字符串能否被單詞列表里的單詞組成)，
并且 i+1 到 j 組成的單詞在列表中能找到，則dp[j] = true
3、初始化
dp[0] = true
其余為false
例如：
string s = "catsandog";
vector<string> wordDict = { "cats", "dog", "sand", "and", "cat" };
dp[2] , j = 2, i = 0時，0-2的cat可以被找到，并且依賴于dp[0]，所以dp[0] 必須為true
4、遍歷順序
構(gòu)成字符串的單詞順序是唯一的，所以是求排列問題，{1，5}和{5，1}是兩種不同的答案。
所以外層遍歷背包，內(nèi)層遍歷物品。
5、舉例推導(dǎo)dp[i]
自己寫的：內(nèi)層遍歷直接就是單詞列表
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
vector<bool> dp(s.size() + 1, 0);
dp[0] = true;
for (int j = 0; j <= s.size(); ++j) {
for (int i = 0; i < wordDict.size(); ++i) {
string temp = wordDict[i];
if (j >= temp.size() && dp[j - temp.size()] == true && s.substr(j - temp.size(), temp.size()) == temp) dp[j] = true;
}
}
return dp[s.size()];
}
};
卡哥寫的：內(nèi)層是在從0開始遍歷字符串，到 j 。看i-j組成的單詞能否被找到
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
vector<bool> dp(s.size() + 1, false);
dp[0] = true;
for (int i = 1; i <= s.size(); i++) { // 遍歷背包
for (int j = 0; j < i; j++) { // 遍歷物品
string word = s.substr(j, i - j); //substr(起始位置，截取的個數(shù))
if (wordSet.find(word) != wordSet.end() && dp[j]) {
dp[i] = true;
}
}
}
return dp[s.size()];
}
};
多重背包理論基礎(chǔ)
每件物品最多有Mi件可用，把Mi件攤開，其實就是一個01背包問題了。
例如：
背包最大重量為10。
物品為：
重量 價值 數(shù)量
物品0 1 15 2
物品1 3 20 3
物品2 4 30 2
問背包能背的物品最大價值是多少？
和如下情況有區(qū)別么？
重量 價值 數(shù)量
物品0 1 15 1
物品0 1 15 1
物品1 3 20 1
物品1 3 20 1
物品1 3 20 1
物品2 4 30 1
物品2 4 30 1文章來源：http://www.zghlxwxcb.cn/news/detail-432860.html
毫無區(qū)別，這就轉(zhuǎn)成了一個01背包問題了，且每個物品只用一次。文章來源地址http://www.zghlxwxcb.cn/news/detail-432860.html
void test_multi_pack() {
vector<int> weight = {1, 3, 4};
vector<int> value = {15, 20, 30};
vector<int> nums = {2, 3, 2};
int bagWeight = 10;
for (int i = 0; i < nums.size(); i++) {
while (nums[i] > 1) { // nums[i]保留到1，把其他物品都展開
weight.push_back(weight[i]);
value.push_back(value[i]);
nums[i]--;
}
}
vector<int> dp(bagWeight + 1, 0);
for(int i = 0; i < weight.size(); i++) { // 遍歷物品
for(int j = bagWeight; j >= weight[i]; j--) { // 遍歷背包容量
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
for (int j = 0; j <= bagWeight; j++) {
cout << dp[j] << " ";
}
cout << endl;
}
cout << dp[bagWeight] << endl;
}
到了這里，關(guān)于算法 DAY45 動態(tài)規(guī)劃07 70. 爬樓梯 322. 零錢兌換 279. 完全平方數(shù) 139. 單詞拆分 多重背包的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
