此处我们介绍一维数组解决背包问题的解法。
面试过程中常见的题型主要为以下两种：
- 0-1 背包：对于每个元素来说，只有两个选：选和不选；也就是说，每个元素只能选取一次
- 完全背包：每个元素可以重复选择
而每个背包要求的问题也是不同的，按照问题分类，又可以分为：
- 最值问题：最大值/最小值
- 存在问题：是否存在…，满足…
- 计数问题：求所有满足…的排列组合，有的题目只要求计算总数，有的要求列举详情
1 解题模版
背包问题大体的解题模板是两层循环，分别遍历物品 nums 和背包容量 target，然后写状态转移方程。
根据背包的分类我们确定物品和容量遍历的先后顺序，根据问题的分类确定状态转移方程的写法。
首先是背包分类的模板：
- 0-1 背包：外循环 nums，内循环 target，target 倒序
- 完全背包：外循环，内循环 随意，target 正序
然后是问题分类的模板：有没有？有几种？最值是？
- 存在问题：dp[i] |= dp[i – num]
- 计数问题：dp[i] += dp[i – num]
- 最值问题：dp[i] = max/min(dp[i], dp[i – num] + 1)
2 o-1背包
2.1 分割等和子集
2.2 目标和
3 完全背包
3.1 零钱兑换
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins =[1, 2, 5], amount =11输出：3解释：11 = 5 + 5 + 1
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
int size = coins.size();
vector<long> dp(amount+1, INT_MAX);
dp[0] = 0;
for(int i = 0; i<size; i++){
for(int j = 1; j<=amount; j++){
if (j < coins[i]) continue;
else dp[j] = min(dp[j], dp[j-coins[i]]+1);
}
}
return dp[amount] == INT_MAX ? -1 : dp[amount];
}
};3.2 单词拆分
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
示例 1：
输入: s = "leetcode", wordDict = ["leet", "code"] 输出: true 解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
vector<bool> dp(s.size()+1, false);
dp[0] = true;
for(int i=1; i<=s.size(); i++){
for(auto word : wordDict){
int size = word.size();
if (i - size >= 0 && s.substr(i-size, size)==word)
dp[i] = dp[i] || dp[i - size];
}
}
return dp[s.size()];
}
};