139.單詞拆分

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);if(wordSet.find(word) != wordSet.end() && dp[j]) {dp[i] = true;}}}return dp[s.size()];}
};

多重背包

關于多重背包，你該了解這些！
https://programmercarl.com/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80%E5%A4%9A%E9%87%8D%E8%83%8C%E5%8C%85.html

#include <bits/stdc++.h>
using namespace std;int main() {int bagWeight,n;cin>>bagWeight>>n;vector<int> weight(n,0);vector<int> value(n,0);vector<int> nums(n,0);for(int i=0;i<n;i++)cin>>weight[i];for(int i=0;i<n;i++)cin>>value[i];for(int i=0;i<n;i++)cin>>nums[i];vector<int> dp(bagWeight+1,0);for(int i=0;i<n;i++) {for(int j=bagWeight;j>=weight[i];j--) {//關鍵代碼在這類，多加了一層物品數量的循環for(int k=1;k<=nums[i] && (j-k*weight[i])>=0;k++) {dp[j] = max(dp[j],dp[j-k*weight[i]]+k*value[i]);            }}}cout<<dp[bagWeight]<<endl;
}

背包問題總結

背包問題總結篇！
https://programmercarl.com/%E8%83%8C%E5%8C%85%E6%80%BB%E7%BB%93%E7%AF%87.html

在前幾天做題過程中，能夠明顯感覺到關于背包問題這個解題思路十分的類似，面對具體問題時的遞推公式也有所差別。

①背包問題的類型判斷總結：

②動規五部曲：

③遞推公式上的小差別：

④遍歷順序