322.零钱兑换
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
题目链接
个人题解
class Solution {
public:int coinChange(vector<int>& coins, int amount) {//先物品后背包vector<int> dp(amount+1,100005);dp[0]=0;for(int i=0;i<coins.size();i++){for(int j=coins[i];j<=amount;j++){dp[j]=min(dp[j-coins[i]]+1,dp[j]);}}if(dp[amount]==100005) return -1;else return dp[amount];}
};
复杂度分析
- 时间复杂度：N*M
- 空间复杂度：N
解题思路
完全背包问题，求组合，故先物品后背包，这里最后求得是装满背包的最少物品数，所以dp内记录使用0-i物品装满j背包所需最小物品数即可，递推逻辑，min(不装这个物品0~i-1物品装满背包物品数的最小值，装上这个物品后剩余重量装满所需的最小物品数的最小值)。递推公式：dp[j]=min(dp[j-weight[i]]+1,dp[j]);注意这里用了min，所以为了初始化要取一个最大值，第一次遍历才能正确的更新。
279.完全平方数
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
题目链接
个人题解
class Solution {
public:int numSquares(int n) {vector<int> dp(n+1,100005);dp[0]=0;for(int i=1;i*i<=n;i++){for(int j=i*i;j<=n;j++){dp[j]=min(dp[j],dp[j-i*i]+1);}}return dp[n];}
};
复杂度分析
- 时间复杂度：N*sqrt(N)
- 空间复杂度：N
解题思路
和上一题一样的思路求的是装满背包的最小物品数，这道题中，背包大小是N，物品是小于N的所以完全平方数，其值等于重量和价值，递推逻辑同上
139.单词拆分
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
题目链接
个人题解
class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {vector<bool> dp(s.size()+1,false);dp[0]=true;for(int j=1;j<=s.size();j++){for(int i=0;i<wordDict.size();i++){if(wordDict[i].size()<=j&&dp[j]==false){dp[j]=(s.substr(j-wordDict[i].size(),wordDict[i].size())==wordDict[i])&&dp[j-wordDict[i].size()];}}}return dp[s.size()];}
};
复杂度分析
- 时间复杂度：N*M
- 空间复杂度：N
解题思路
排列问题先背包后物品，这里背包是s,物品是wordDict，最后只求是否能装满背包，因此dp只记录布尔类型数据就可以，对于dp[j]是否为真，遍历每一个物品时，先判断这个物品能不能与0-j的字符尾串相等，然后再查看尾串之前的部分是不是true（是不是可以装满），两者都满足就改成true，另外，是先背包后物品遍历，对于每一种重量，只要有一个物品匹配且使这个格为true，那么其他部分便不用考虑，也就是说，在二维层面上，竖着的一列，有一个格子是true，那么这个重量就算可以匹配，换到一维上就是只有该格为false时才进行计算（不加这个条件会导致后面物品的计算结果把有匹配成功的结果覆盖掉）
今日总结
今天是完全背包的应用
发现前两道题4个月前做过，现在看自己当时写的已经完全没印象了，当时应该都没学完全背包
今天又见到了一些新的dp要求，求装满背包的最少物品数（组合），递推公式：dp[j]=min(dp[j],dp[j-weight[i]]+1);
字符串这个处理相当特殊，不作为公式了，后面遇到一个想一个吧
