322. 零钱兑换 - 力扣（LeetCode）
思路：完全背包，初始化为最大背包容量，当背包为0的时候有0枚硬币
重点：dp[i-coins[j]]+1,统计个数
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
int n=coins.size();
vector<int>dp(amount+1,amount+1);//设置背包初始值
dp[0]=0;//当背包为0的时候有0枚硬币
for(int i=1;i<=amount;i++){//遍历背包
for(int j=0;j<n;j++){//遍历物品
if(coins[j]<=i)//物品重量小于等于背包容量
dp[i]=min(dp[i],dp[i-coins[j]]+1);
}
}
return dp[amount]>amount?-1:dp[amount];
}
};
279. 完全平方数 - 力扣（LeetCode）
思路：完全背包，n是背包，从1开始的平方数是物品。先遍历背包再遍历物品
重点：dp[i-j*j]+1
class Solution {
public:
int numSquares(int n) {
vector<int>dp(n+1,10001);
dp[0]=0;
for(int i=0;i<=n;i++){//遍历背包
for(int j=1;j*j<=i;j++){//遍历物品
dp[i]=min(dp[i],dp[i-j*j]+1);
}
}
return dp[n];
}
};139. 单词拆分 - 力扣（LeetCode）
思路：利用哈希表存放字典的单词，dp[i]表示字符串长度为i时由字典中的一个或者多个单词组成。
重点：遍历每一个区间的子串。如果当前下标j开始的子串不能与字典匹配则跳过
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
int n=s.size();
//把所有单词放入哈希表中
unordered_set<string>hash(wordDict.begin(),wordDict.end());
vector<bool>dp(n+1,false);
dp[0]=true;//初始化dp[0]数组为true，基于此递推
for(int i=1;i<=n;i++){//遍历背包
for(int j=0;j<i;j++){//遍历物品
string word=s.substr(j,i-j);//遍历从j到i区间的所有子串
if(hash.find(word)!=hash.end()&&dp[j]){//如果当前开始的子串不能与字典匹配则跳过
dp[i]=true;
}
}
}
return dp[n];
}
};总结
遇到求数量题可以尝试使用递推公式为dp[j-weight[i]]+1
