322.零钱兑换
思路
读题可知，典型的完全背包问题，不同点在于所求为最小的元素个数。
在五部曲时动手列一列就好了，既然递推公式求min，如何初始化？dp[0]如何处理？越界问题如何处理？
都要想清楚。
题解
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
vector<int> dp(amount+1,INT_MAX);
dp[0] = 0;//拉下，一定记住五部曲
for(int i = 0;i<coins.size();i++)
{
for(int j = coins[i];j<=amount;j++)
{
if(dp[j-coins[i]] != INT_MAX)
{
dp[j] = min(dp[j],dp[j-coins[i]]+1);
}
}
}
if(dp[amount] == INT_MAX)return -1;
else return dp[amount];
}
};
279.完全平方数
思路
秒了，与上题类似，但是本题在物品重量（数的平方）上作了文章。
同样注意dp[0]与INT_MAX的辨析。
题解
class Solution {
public:
int numSquares(int n) {
vector<int> dp(n+1,INT_MAX);
dp[0] = 0;
for(int i = 0;i*i<=n;i++)
{
for(int j = i*i;j<=n;j++)
{
if(dp[j-(i*i)]!=INT_MAX)
{
dp[j] = min(dp[j-(i*i)]+1,dp[j]);
}
}
}
return dp[n];
}
};
139.单词拆分
思路
同样类似于完全背包问题，本题所求是否存在性问题，联想到之前weight = value。
继而推出存在条件：dp[s.size()] = s。
继续向前推导，什么时候可以将遍历的字符串假如？temp.size() == j && s.find(temp) == 0，二者缺一不可。
第一个条件包含weight = value，砍去了背包非最优情况；
第二个条件保证添加字符串的正确（深刻理解，当时没想到）。
题解
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
vector<string> dp(s.size()+1,"");
for(int j = 0;j<=s.size();j++)
{
for(int i = 0;i<wordDict.size();i++)
{
if(j>=wordDict[i].size())
{
string temp = dp[j-wordDict[i].size()]+wordDict[i];
if(temp.size() == j && s.find(temp) == 0)dp[j] = temp;
}
}
}
if(dp[s.size()] == s)return true;
else return false;
}
};
多重背包问题
题目链接：56.携带矿石资源（第八期模拟笔试）
文档讲解：代码随想录
状态：类似01背包
思路
相比01背包，多了物品的使用次数，最笨最有效的方法：按照物品次数在weight与value数组中添加相应数据即可，后面就是01背包问题。
更优雅的方法：在遍历背包过程中操作：
对应每个dp[j]，进行一个物品次数for循环，再能添加多次的情况下分别比较取max即可。
多重背包作为了解，知道其与01背包的紧密联系简单分析就行哇。
题解
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int bagsize = 0, N = 0;
cin>>bagsize>>N;
vector<int> weight(N,0);
vector<int> value(N,0);
vector<int> num(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>>num[i];
vector<int> dp(bagsize+1);
for(int i = 0;i<N;i++)
{
for(int j = bagsize;j>=weight[i];j--)
{
for(int k = 1;k<=num[i] && weight[i]*k<=j;k++)
{
dp[j] = max(dp[j],dp[j-weight[i]*k]+value[i]*k);
}
}
}
cout<<dp[bagsize]<<endl;
return 0;
}
背包问题总结
常见背包问题分类：
背包问题，本意解决拿物品放背包->价值最大，后延申为拿元素排列->目标最优（数量、价值、次数等等等）。
这就让我们灵活变通dp含义以及各种类型的初始化，五部分都要考虑周全。
1.01背包：一维数组遍历时了解为什么从后往前遍历
2.完全背包：排列组合问题与遍历顺序的关系
3.多重背包：如何转化为01背包解答
在分析背包问题时，牢记dp数组含义，二维结合一维分析，考虑周全！！！
最后放一张欣炜图：
图片来源于 知识星球-海螺人