題目鏈接： 322. 零錢兌換 - 力扣（LeetCode）

文章講解： 代碼隨想錄

思路：

確定遞推公式：

dp[j]=min(dp[j],dp[j-coins[i]]+1);?

由于是完全背包 ，所以遍歷順序是正序

還存在另一個問題 沒有任何一種硬幣組合能組成總金額

其實也就是沒更新 dp?

class Solution {
public:int coinChange(vector<int>& coins, int amount) {vector<double>dp2(amount+1,0);dp2[0]=0;for(int i=0;i<coins.size();i++){for(int j=coins[i];j<=amount;j++){dp2[j]=max(dp2[j],dp2[j-coins[i]]+coins[i]);}}if(dp2[amount]!=amount)return -1;vector<int>dp(amount+1,INT_MAX-2);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);}}return dp[amount];}
};

需要注意的是：完全背包的兩層for循環強調先后順序

但是排列 或組合問題是強調先后順序的

class Solution {
public:int numSquares(int n) {vector<int>nums;for(int i=1;i<=sqrt(n);i++){nums.push_back(i*i);}vector<int>dp(n+1,INT_MAX);dp[0]=0;for(int i=0;i<nums.size();i++){for(int j=nums[i];j<=n;j++){dp[j]=min(dp[j],dp[j-nums[i]]+1);}}return dp[n];}
};

?思路：

這道題可以理解為一個完全背包問題

那么需要考慮 背包容量 物品?

物品就是單詞

背包容量呢 就是字符串s的長度

完全背包 那么是排列問題還是組合問題 這是排列問題 所以先遍歷背包

dp[i]表示前i個字符能被分割

字符串有函數s.substr(i,n)表示從位置i開始分割長度為n的字符串

注意遞推公式：

class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {unordered_set<string>myset(wordDict.begin(),wordDict.end());vector<bool>dp(s.size()+1,false);dp[0]=true;for(int i=1;i<dp.size();i++){   for(int j=0;j<i;j++){string word=s.substr(j,i-j);if(myset.find(word)!=myset.end()&&dp[j]==true) {dp[i]=true;}}}return dp[s.size()];}
};