1.322零钱兑换
与昨天的零钱兑换问题的区别主要不同点在于dp数组的含义，相同点都是属于组合问题。
1.dp数组的含义：dp[j]:代表容量为j时候的最少零钱个数
2.递推公式：dp[j] = min(dp[j],dp[j-coins[i]]+1);dp[j-coins[i]]+1 = dp[j - weight[i]]+value[i],所以还是属于一个变式。因为题目要求的是最小个数，所以得取min函数。
3.初始化：由于要取最小值，所以一开始初始化的时候不能设置为0，而是应该设置一个超过其对应范围的个数，可以是INT_32，也可以是10001因为题目中规定的范围是10000.但是dp[0] = 0,因为容量为0时放不进去零钱，所以为0.
4.因为这个题目里面需要的是最小的个数，这属于组合问题里面的一个叶子节点，所以遍历方式是先遍历种类再遍历容量。
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
sort(coins.begin(),coins.end());//先排序
vector<int> dp(amount+1,10001);//dp[i]:价格为i的时候的最小的硬币个数
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);
}
}
//if(amount == 0) return 0;
if (dp[amount] == 10001) return -1;
return dp[amount];
}
};2.279完全平方数
1.dp数组的含义：dp[j]:代表容量为j时候的最少得完全平方数个数
2.递推公式：dp[j]= min(dp[j],dp[j-i*i]+1);dp[j-i*i]+1 = dp[j - weight[i]]+value[i],所以还是属于一个变式。因为题目要求的是最少个数，所以得取min函数。
3.初始化：由于要取最小值，所以一开始初始化的时候不能设置为0，而是应该设置一个超过其对应范围的个数，可以是INT_32，也可以是10001因为题目中规定的范围是10000.但是dp[0] = 0,因为容量为0时没有完全平方数，所以为0.
4.遍历顺序：因为这个题目里面需要的是最小的个数，这属于组合问题里面的一个叶子节点，所以遍历方式是先遍历种类再遍历容量。
整体下来和前面的类似。
class Solution {
public:
int numSquares(int n) {
vector<int> dp(n+1,10001);//dp[i]:容量为i的最少数量
dp[0] = 0;
for(int j = 1;j<=n;j++){
for(int i = 1;i*i<=n;i++){
if(j>=i*i)dp[j]= min(dp[j],dp[j-i*i]+1);
}
}
return dp[n];
}
};3.139单词拆分
1.dp数组的含义：dp[j]:容量为j的时候能否被拆分
2.递推公式：分三种情况：1.当dp[j-m](m为需要匹配的那个字典的长度)为false的时候直接返回false.2.当和这一段出现false的时候，结果为false。3.当dp[j-m]为true的同时这一段也能匹配，结果为true，然后break，代表这个长度可以匹配成功。
3.初始化：默认情况下为true，但是dp[0]为true.保证递推能够正常进行下去。
4.遍历顺序：这是属于完全背包下面的排列问题（因为要考虑顺序），所以是先遍历容量再遍历物品。
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
int n = s.size();
//这个应该是一个排列的问题，是需要考虑顺序的，所以应该先遍历容量
vector<bool> dp(n+1,false);//dp[i]:长度为i的是否能够被找到
dp[0] = true;//初始化
for(int j = 1;j<=n;j++){//遍历背包容量
for(auto& word:wordDict){//遍历物品
int m = word.size();
if(j >= m){
if(dp[j-m] == false){//如果前面那个是false，那么直接返回false
dp[j] = false;
continue;
}
bool ischeck = true;
for(int k = 0;k<m;k++){//用来判断这一段是否能够匹配
if(s[j-m+k]!=word[k]){
ischeck = false;
break;
}
}
if(ischeck == true){//代表这一段匹配了，递推公式
dp[j] = true;
break;//找到了之后，后面的就不需要再找了
}else{
dp[j] = false;
}
}
}
}
return dp[n];
}
};
