05.03 背包问题
滚动数组优化：
$dp[w] = \begin{cases} dp[w] & w < weight[i - 1] \cr max \lbrace dp[w], dp[w - weight[i - 1]] + value[i - 1] \rbrace & w \ge weight[i - 1] \end{cases}$
分析
先把数组的和求出来，然后转化成01背包问题，即找到能够装入sum/2的。
- 划分阶段：按照当前背包的载重上限进行阶段划分。
- 定义状态：定义状态dp[w]表示为：从数组nums中选择一些元素，放入最多能装元素和为w的背包中，得到的元素和最大为多少。
- 状态转移方程：$dp[w] = \begin{cases} dp[w] & w < nums[i - 1] \cr max \lbrace dp[w], \quad dp[w - nums[i - 1]] + nums[i - 1] \rbrace & w \ge nums[i - 1] \end{cases}$
- 初始条件：无论背包载重上限为多少，只要不选择物品，可以获得的最大价值一定是0，即dp[w] = 0.
- 返回结果：最后判断dp[target]是否等于target。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class Solution {
public:
bool canPartition(vector<int>& nums) {
int n = nums.size();
int sum = 0;
for(int i = 0; i < n; i++){
sum += nums[i];
}
if(sum % 2){
return false;
}
int target = sum / 2;
vector<int> dp(target + 1);
int weight = target;
for(int i = 1; i <= n; i++){
for(int w = weight; w >= nums[i-1]; w--){
dp[w] = max(dp[w], dp[w-nums[i-1]] + nums[i-1]);
}
}
return dp[target] == target;
}
};
|
- 时间复杂度：$O(n \times target)$
- 空间复杂度：$O(target)$
分析
之前在记忆化搜索部分做过这道题，这里用动态规划再做一遍。
数组中所有前面为＋的数字和记为sum_x，为-的数字和记为sum_y，则target = sum_x - sum_y，而sum = sum_x + sum_y，可以推出sum_x = (sum + target) / 2，转化问题为如何在数组中找到一个集合，使集合中元素和为sum_x = (sum + target) / 2，背包容量为sum_x = (sum + target) / 2的01背包问题。
- 定义状态：dp[i]表示填满容量为i的方法数。
- 状态转移方程：
- 不使用当前数字：dp[i]
- 使用当前数字：dp[i-num]
dp[i] = dp[i] + dp[i-num]
3. 初始化：默认填满容量为0的背包方法有1种，即dp[i] = 1.
4. 返回结果：dp[n]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
int n = nums.size();
int sum = 0;
for(int i = 0; i < n; i++){
sum += nums[i];
}
if(abs(target) > abs(sum) || (sum+target) % 2){
return 0;
}
int weight = (sum + target) / 2;
vector<int> dp(weight + 1);
dp[0] = 1;
for(int i = 1; i <= n; i++){
for(int w = weight; w >= nums[i-1]; w--){
dp[w] = dp[w] + dp[w-nums[i-1]];
}
}
return dp[weight];
}
};
|
- 时间复杂度：$O(n \times weight)$
- 空间复杂度：O(weight)
分析
问题转化为：把一堆石头尽量平均的分成两对，求两堆石头重量差的最小值。两堆石头的重量要尽可能的接近数组总数量和的一半。先对所有重量求和，然后target=sum/2，转化为容量为target/2的01背包。
- 划分阶段：按照石头的序号进行阶段划分。
- 定义状态：dp[w]表示在容量为w时的价值。
- 状态转移方程：
dp[w] = max(dp[w], dp[w-stones[i-1]] + nums[i-1])
- 初始条件：dp[w] = 0
- 返回结果：sum - dp[target] - dp[target]。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public:
int lastStoneWeightII(vector<int>& stones) {
int n = stones.size();
int sum = 0;
for(int i = 0; i < n; i++){
sum += stones[i];
}
int target = sum / 2;
vector<int> dp(target + 1);
for(int i = 1; i <= n; i++){
for(int w = target; w >= stones[i-1]; w--){
dp[w] = max(dp[w], dp[w-stones[i-1]]+stones[i-1]);
}
}
return sum - dp[target] * 2;
}
};
|
- 时间复杂度：$O(n \times target)$
- 空间复杂度：O(target)
第八天
广度优先搜索
- 定义集合visited避免重复计算，定义队列存放节点，定义count为完全平方数的最小数量。
- 初始化：将n标记为Visited，并加入队列。
- 依次将队列中的节点值取出，count+1。
- 对于取出的节点值，遍历可能出现的平方数，即从$[1, \sqrt {value} + 1]$
- 每次从当前节点值减去一个平方数，并将减完的数加入队列。
- 如果此时的数等于0，则满足题意，返回当前树的最小深度。
- 如果此时的数不等于0，则将其加入队列，继续查找。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| class Solution {
public:
int numSquares(int n) {
unordered_set<int> visited;
queue<int> que;
int count = 0;
visited.insert(n);
que.push(n);
while(!que.empty()){
count++;
int size = que.size();
for(int i = 0; i < size; i++){
int value = que.front();
que.pop();
for(int v = 1; v <= sqrt(value)+1; v++){
int x = value - v * v;
if(x == 0){
return count;
}
if(visited.find(x) == visited.end()){
que.push(x);
visited.insert(x);
}
}
}
}
return count;
}
};
|
- 时间复杂度：$O(n \times \sqrt{n})$
- 空间复杂度：O(n)
动态规划
将题目转化成01背包问题。将$k=1,2,4,9…$当成k种物品，每种物品都可以无限次使用。将n看成背包的容量。即，用K种物品装入容量为n的背包，所需要的最少物品数。
- 划分阶段：按照当前背包的载重上限进行阶段划分。
- 定义状态：dp[w]表示从完全平方数中挑选一些数，使其和恰好凑w所需的最少个完全平方数。
- 状态转移方程：
dp[w] = min(dp[w], dp[w-num]+1)
- 初始条件：
dp[0]=0，对于其他状态，则为无限大，可以设置为n+1.
- 返回结果：dp[n]。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
int numSquares(int n) {
vector<int> dp(n+1, n+1);
dp[0] = 0;
for(int i = 1; i <= sqrt(n)+1; i++){
int num = i * i;
for(int w = num; w <= n; w++){
dp[w] = min(dp[w], dp[w-num]+1);
}
}
return dp[n];
}
};
|
- 时间复杂度：$O(n \times \sqrt{n})$
- 空间复杂度：O(n)
分析
- 划分阶段：按照背包容量即金额进行阶段划分。
- 定义状态：dp[i]表示凑成i元需要的最少硬币数。
- 状态转移方程：
dp[i] = min(dp[i], dp[i-num]+1)
- 初始条件：凑成总金额为0所需的最少硬币数为0，dp[0]=0
- 返回结果：dp[n]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
vector<int> dp(amount + 1, INT_MAX-1);
dp[0] = 0;
for(int coin : coins){
for(int i = coin; i <= amount; i++){
dp[i] = min(dp[i], dp[i - coin] + 1);
}
}
return dp[amount] == (INT_MAX-1) ? -1 : dp[amount];
}
};
|
- 时间复杂度：$O(amount \times size)$。
- 空间复杂度：O(amount)
分析
- 划分阶段：按照背包容量即金额进行阶段划分。
- 定义状态：dp[i]表示凑成i元有多少种组合方式。
- 状态转移方程：不使用当前coin+使用当前coin。即
dp[i] = dp[i] + dp[i-coin]
- 初始条件：凑成总金额为0的组合方式只有1种。
- 返回结果：dp[n]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
int change(int amount, vector<int>& coins) {
vector<int> dp(amount + 1);
dp[0] = 1;
for(int coin : coins){
for(int i = coin; i <= amount; i++){
dp[i] = (long long)dp[i] + (long long)dp[i-coin];
}
}
return dp[amount];
}
};
|
- 时间复杂度：$O(n \times amount)$
- 空间复杂度：O(amount)
分析
- 划分阶段：按照单词结尾位置进行阶段划分。
- 定义状态： 能否拆分为单词表的单词，可以分解为：前i个字符构成的字符串，能否分解为单词；剩余字符串，能否分解为单词。dp[i]表示前i个字符组成的字符串是否可以拆分成单词表的单词。
- 状态转移数组：如果s[0:j]可以拆分，即
dp[j]=true，并且s[j:i]出现在字典中，则dp[i] = true。如果s[0:j]不可以拆分，或者s[j:i]没有出现在字典中，则dp[i] = false。
- 初始条件：长度为0的字符串可以拆分为单词，
dp[0] = true。
- 返回结果：dp[n]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
int n = s.length();
vector<bool> dp(n + 1);
dp[0] = true;
unordered_set<string> set;
for(string str : wordDict){
set.insert(str);
}
for(int i = 0; i <= n; i++){
for(int j = 0; j < i; j++){
string sub = s.substr(j, i-j);
if(dp[j] && set.find(sub) != set.end()){
dp[i] = true;
}
}
}
return dp[n];
}
};
|
- 时间复杂度：$O(n^2)$
- 空间复杂度：O(n)
分析
本题与「完全背包问题求方案数」不同点在于：方案中不同的物品顺序代表不同方案。我们需要在考虑某一总和 时，需要将所有元素都考虑到。对应到循环关系时，即将总和的遍历放到外侧循环，将数组元素的遍历放到内侧循环。
- 划分阶段：按照target进行阶段划分。
- 定义状态：dp[i]表示凑成i所有的组合方式数。
- 状态转移方程：
dp[i] = dp[i] + dp[i-num]
- 初始条件：凑成0元有一种组合方式，
dp[0] = 1。
- 返回结果：dp[target]。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
vector<int> dp(target + 1);
dp[0] = 1;
for(int i = 0; i <= target; i++){
for(int num : nums){
if(i >= num){
dp[i] += (long long)dp[i-num];
}
}
}
return dp[target];
}
};
|
- 时间复杂度：$O(n \times target)$
- 空间复杂度：O(target)
分析
- 划分阶段：按照总价值target划分。
- 定义状态：dp[w]表示用n个骰子进行投掷，投掷出总和（总价值）为w的方案数。
- 状态转移方程：
dp[w] = dp[w] + dp[w-d]，d为当前骰子投出的价值。
- 初始条件：dp[0] = 1.
- 返回结果：dp[target]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public:
int numRollsToTarget(int n, int k, int target) {
long long mod = 1000000007;;
vector<int> dp(target + 1);
dp[0] = 1;
for(int i = 0; i < n; i++){
for(int w = target; w >= 0; w--){
dp[w] = 0;
for(int d = 1; d <= k; d++){
if(w >= d){
dp[w] = (dp[w] + dp[w-d]) % mod;
}
}
}
}
return dp[target] % mod;
}
};
|
- 时间复杂度：$O(n \times m \times target)$。
- 空间复杂度：O(target)
分析
把0的个数和1的个数视作一个二维背包的容量。每一个字符串都当做是一件物品，其成本为字符串中1的数量和0的数量，每个字符串的价值为1。
- 划分阶段：按照物品的序号、当前背包的载重上限进行阶段划分。
- 定义状态：dp[i][j]表示最多有i个0、j个1的字符串strs的最大子集的大小。
- 状态转移方程：
- 使用之前字符串填满容量为
i-numZero、j-numOne的背包物品数+当前字符串价值。
- 选择之前字符串填满容量为i、j的物品数。
- $dp[i][j] = max(dp[i][j], dp[i - zero\underline{\hspace{0.5em}}num][j - one\underline{\hspace{0.5em}}num] + 1)$
- 初始条件：dp[i][0] = dp[0][j] = 0
- 返回结果：dp[m][n]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
vector<vector<int>> dp(m+1, vector<int>(n+1));
for(string str : strs){
int numZero = 0;
int numOne = 0;
for(char ch : str){
if(ch == '0'){
numZero++;
}
else{
numOne++;
}
}
for(int i = m; i >= numZero; i--){
for(int j = n; j >= numOne; j--){
dp[i][j] = max(dp[i][j], dp[i-numZero][j-numOne] + 1);
}
}
}
return dp[m][n];
}
};
|
- 时间复杂度：$O(len \times m \times n)$
- 空间复杂度：O(mn)
剩余题目
总结
01背包中不同物体只有一个，也就是说对于任一物体，只有选或不选两种选择，而完全背包又是也是01背包稍作变化而来，即：完全背包的物品数量是无限的。