(背包dp) 力扣背包dp 题集记录

天赐细莲

2824

2022.09.18

2024.02.01

发布于未知归属地

动态规划 C++背包问题学习分享

前言
1. 🔖思路与技巧
题单
END

前言

背包基础：(背包dp) 背包N讲_天赐细莲的博客-CSDN博客_背包dp

楼主深刻感到自己动归的水平太差

痛定思痛，决定爆刷一些dp的题

因此在力扣上搜集了一些背包dp的题练习下，以本文作为记录

注意：本文不适合连01背包都不会的小白观看，且不会写过多文字作题解，一些尽在代码中

小白可以先把我上面那篇博客学完了再来练习本文的题集

🔖思路与技巧

背包dp是很多地方将动态规划的一个入门类型。但是背包dp并不是最简单的一种，甚至有一定难度。

背包dp中包含很多动态规划中的重要思想。

多维的状态表示，状态的转移，转移的判断条件，多维的降维方式，滚动数组表示，逆序便利的特点，等等等等。

题单

🏷️139. 单词拆分

⭐判断能否正好装满背包 + 完全背包 + 优先遍历容量

题意与要求

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

用bool数组即可，需要明确定自己定义dp[]的含义和可以转移的条件

如下方代码中，dp[]表示以idx位置为结尾，能否连接上单词

Code

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int n = s.size();
        vector<bool> dp(n + 1);
        dp[0] = true;
        // 每个位置为结尾，能否连接上单词
        for (int j = 1; j <= n; j++) {
            for (string & t : wordDict) {
                int len = t.size();
                int i = j - len + 1;
                // 这里的i表示含义比较多
                if (i > 0 && dp[i - 1] && s.substr(i - 1, len) == t) {
                    dp[j] = true;
                    break;
                }
            }
        }

        return dp[n];
    }
};

🏷️279. 完全平方数

⭐选取数

题意与要求

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量。

选取数一般是dp初始为最大值

转移方程为min(+1)型

Code

class Solution {
public:
    int numSquares(int n) {
        // 求最小值，则初始化最大或无穷大
        vector<int> dp(n + 1, INT_MAX / 2);
        // 0个数，容纳0个空间
        dp[0] = 0;
        // 遍历物品 (完全平方数)
        for (int i = 1; i * i <= n; i++) {
            int num = i * i;
            // 完全背包
            for (int j = num; j <= n; j++) {
                dp[j] = min(dp[j], dp[j - num] + 1);
            }
        }

        return dp[n];
    }
};

🏷️322. 零钱兑换

⭐选取数

题意与要求

凑成总金额所需的 最少的硬币个数

本题一个要点就是需要正好完全利用空间

本题也是典型的选取数，但是并不保证能正好容纳最终的空间，因此在处理时候要加判断

且INT_MIN+1会越界

Code

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        // 定义最少需要数量，初始无穷个
        vector<int> dp(amount+1, INT_MAX);
        // 0空间放0个
        dp[0] = 0;
        for (int x : coins) {
            // 完全背包
            for (int j = x; j <= amount; j++) {
                // 已经利用过才能转化，保证空间完全利用
                if (dp[j - x] != INT_MAX) {
                    dp[j] = min(dp[j], dp[j - x] + 1);
                }
            }
        }
        return dp[amount] == INT_MAX ? -1 : dp[amount];
    }
};

🏷️377. 组合总和 Ⅳ

⭐方案数 + 完全背包 + 优先遍历空间

题意与要求

给你一个由不同整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

这种题是一样算方案数，且[1, 2]和[2, 1]算作不同方案

就要很敏感的想到先遍历空间

Code

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        // 题目数据保证答案符合 32 位整数范围
        // 以为是废话，实际是提示
        vector<unsigned> dp(target + 1);
        dp[0] = 1;
        // 先遍历空间
        for (int j = 0; j <= target; j++) {
            // 再遍历物品
            for (int x : nums) {
                // dp[] < INT_MAX - dp[ - x]
                if (j - x >= 0) {
                    dp[j] += dp[j - x];
                }
            }
        }

        return dp[target];
    }
};

🏷️416. 分割等和子集

⭐num既是容量又是价值

题意与要求

判断将数组能否划分为两个总和相等的集合

就是算dp[half] == half

正好满足V容量型问题

典型的 num既是容量又是价值

Code

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum & 1) {
            return false;
        }

        int half = sum >> 1;
        vector<int> dp(half + 1);
        for (int x : nums) {
            for (int j = half; j >= x; j--) {
                dp[j] = max(dp[j], dp[j - x] + x);
            }
        }

        return dp[half] == half;
    }
};

🏷️474. 一和零

⭐选取数 + 多维度

题意与要求

现有一个01字符串数组

分别限制0和1的数量，求选取数

就是多一个维度而已，思路完全一致

Code

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        // 0个0&0个1的选择个数为0
        dp[0][0] = 0;

        for (string s : strs) {
            int zero = count(s.begin(), s.end(), '0');
            int one = s.size() - zero;
            for (int j = m; j >= zero; j--) {
                for (int k = n; k >= one; k--) {
                    dp[j][k] = max(dp[j][k],  dp[j - zero][k - one] + 1);
                }
            }
        }

        return dp[m][n];
    }
};

🏷️494. 目标和

⭐负数偏移

题意与要求

一串数字，给每个数字添加 +/-号化为一个计算表达式

求能算出目标值的方案数

本题可以通过dfs回溯处理(数据量较小)，官方的dp先通过找到一定数学规律，避免了负数的情况目标和 - 官方题解

但我一般想不到这种化简方式，因此还是用常规的思路处理

这类题一般适合二维的dp，用上一层转化过来，这样就不会使本层混乱

Code

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int n = nums.size();
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (abs(target) > sum) {
            return 0;
        }
        
        // [-sum , 0, sum] ---> [0, sum, 2 * sum]
        vector<int> dp(2 * sum + 1);
        // 1*sum 就是偏移量，原先的0起点
        dp[sum] = 1;
        
        for (int x : nums) {
            // 由上一层转化而来
            auto pre = dp;
            dp = vector<int>(pre.size());
            // 01背包
            for (int j = 0; j < dp.size(); j++) {
                if (j - x >= 0) {
                    dp[j] += pre[j - x];
                }
                if (j + x < dp.size()) {
                    dp[j] += pre[j + x];
                }
            }
        }

        return dp[sum + target];
    }
};

官方写法

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int n = nums.size();
        int sum = accumulate(nums.begin(), nums.end(), 0);
        // 虽然本题有负数，但我们全部用正数的思维来思考
        // sum == diff + target
        int diff = sum - target;
        if (diff < 0 || diff % 2 != 0) {
            return 0;
        }
        // 因为一个数变负号是双倍的效果
        int neg = diff / 2;
        // 标准的01背包，求方案总数
        vector<int> dp(neg + 1);
        dp[0] = 1;
        for (int x : nums) {
            for (int j = neg; j >= x; j--) {
                // 确定容量的计算种类可以直接加
                dp[j] += dp[j - x];
            }
        }

        return dp[neg];
    }
};

🏷️518. 零钱兑换 II

⭐方案数

题意与要求

在 322. 零钱兑换的前提下，计算方案数量

不断累计前面的种类数即可

Code

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        // 定义dp为方案数
        vector<int> dp(amount + 1);
        // 取0个是一种方式
        dp[0] = 1;

        for (int i = 0 ; i < coins.size(); i++) {
            int x = coins[i];
            // 任意放，完全背包
            for (int j = x; j <= amount; j++) {
                // 直接叠加之前的状态
                // 若之前不能放，则dp[]=0不影响答案
                dp[j] += dp[j - x];
            }
        }

        return dp[amount];
    }
};

🏷️879. 盈利计划

⭐背包中的战斗机(完全理解)

本题难度较大

常规dp是定义单个点的定义，本题是一个区间的定义

题意与要求

两个限制，集团员工人数上限 n，以及工作产生的利润下限minProfit

求方案数

定义 dp[i][j][k]

第一维的压缩是基本功

第二维的初始化也有讲究，具体看代码

第三维与寻常的定义不同

工作利润至少为 k

不是 工作利润恰好为 k

Code

// 容量定义，提供使用了j
class Solution {
private:
    const int mod = 1e9 + 7;
public:
    int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
        int N = group.size();
        // 物品 容量 价值
        // 这里的第三维表示，至少有k的价值的量
        // 这样就能把[k, sum]全部集中到一起了
        vector<vector<vector<int>>> dp(N+1, vector<vector<int>>(n+1, vector<int>(minProfit+1)));

        // 任何状态0价值都是一种可能
        for (int i = 0; i <= N; i++) {
            for (int j = 0; j <= n; j++) {
                dp[i][j][0] = 1;
            }
        }

        for (int i = 1; i <= N; i++) {
            int cost = group[i-1], val = profit[i-1];
            // 二维01背包
            for (int j = 0; j <= n; j++) {
                for (int k = 0; k <= minProfit; k++) {
                    // 先直接抄上一层
                    dp[i][j][k] = dp[i-1][j][k];
                    // 可以放得下
                    if (j >= cost) {
                        // 若当前物品价值太大
                        // 大于了当前dp的k，则理想状态是取 负数+val=k
                        // 由于没有负数，则用0+val > k
                        // 再借助定义dp时的k是至少有k的价值
                        // [k, 0+val, sum] ==> 0+val∈[k, sum]
                        int idx = max(0, k-val);
                        dp[i][j][k] = (dp[i][j][k] + dp[i-1][j-cost][idx]) % mod;
                    }
                }
            }
        }

        return dp[N][n][minProfit];
    }
};

// 容量定义，正好是j
class Solution {
private:
    const int mod = 1e9 + 7;
public:
    int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
        int N = group.size();
        // 物品 容量 价值 (把物品数量的第一维压缩)
        // 这里的第三维表示，至少有k的价值的量
        // 这样就能把[k, sum]全部集中到一起了
        vector<vector<int>> dp (n+1, vector<int>(minProfit+1));

        // 刚好使用j的空间，获得价值k
        dp[0][0] = 1;

        for (int i = 1; i <= N; i++) {
            int cost = group[i-1], val = profit[i-1];
            // 一维01背包
            for (int j = n; j >= cost; j--) {
                // 这一维随意，因为是从j <--> j-cost 转化的
                for (int k = minProfit; k >= 0; k--) {
                    int idx = max(0, k-val);
                    dp[j][k] = (dp[j][k] + dp[j-cost][idx]) % mod;
                }
            }
        }

        // 因为本题是可能性计数
        // 所以要把所有正好是j的情况都计上
        int ans = 0;
        for (int j = 0; j <= n; j++) {
            ans = (ans + dp[j][minProfit]) % mod;
        }
        return ans;
    }
};

超时代码，这份code的关键是定义了k为正好多少价值

这样若sum很大时，就会超时

class Solution {
private:
    const int mod = 1e9 + 7;
public:
    int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
        int sum = accumulate(profit.begin(), profit.end(), 0);
        if (sum < minProfit) {
            return 0;
        }

        vector<vector<int>> dp(n + 1, vector<int> (sum + 1));
        // 无论多少人，利润为0都是一种方式
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 1;
        }
        for (int i = 0; i < group.size(); i++) {
            int cost = group[i], val = profit[i];
            // 滚动，保存前面的状态
            auto pre = dp;
            // 人数限制，01背包，先处理大空间
            for (int j = n; j >= cost; j--) {
                // 利润值，到这里确定了两层 j <-> j-cost
                // 因此顺逆序无关，类似二维的01背包
                for (int k = sum; k >= val; k--) {
                    dp[j][k] += dp[j - cost][k - val];
                    dp[j][k] %= mod;
                }
            }
        }

        int ans = 0;
        // 充分利用完n个人后，累计 >= min的数量
        for (int j = minProfit; j <= sum; j++) {
            ans += dp[n][j];
            ans %= mod;
        }

        return ans;
    }
};

🏷️1049. 最后一块石头的重量 II

⭐num既是容量又是价值

题意与要求

每次两个数字相互抵消，并保留差值，求最后可能剩下的最小值

本题有一定思维转化难度目的要让最终值最小

略去证明过程，可以抽象为两堆±的数值，然后比较两堆的差值

因此要尽可能的让两堆的值接近sum / 2

Code

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum = accumulate(stones.begin(), stones.end(), 0);
        int half = sum / 2;

        vector<int> dp(sum + 1);
        for (int x : stones) {
            // 01背包
            for (int j = sum; j >= x; j--) {
                // 体积同时又是价值
                dp[j] = max(dp[j], dp[j - x] + x);
            }
        }

        int half1 = dp[half];
        int half2 = dp[sum] - half1;
        return abs(half1 - half2);
    }
};

🏷️1155. 掷骰子的N种方法

⭐方案数 + 分组背包

题意与要求

这里有 n 个一样的骰子，每个骰子上都有 k 个面，分别标号为 1 到 k 。

给定三个整数 n , k 和 target ，返回可能的方式(从总共 kn 种方式中)滚动骰子的数量，使正面朝上的数字之和等于 target 。

答案可能很大，你需要对 1e9 + 7 取模。

分组背包，每组物品的每个都要尝试，每个状态位保留最优值

Code

class Solution {
private:
    const int mod = 1e9 + 7;
public:
    int numRollsToTarget(int n, int K, int target) {
        vector<vector<int>> dp(n + 1, vector<int>(target + 1));
        // 0个物品0点价值是一种可能
        dp[0][0] = 1;
        // 特殊的分组背包问题
        // 遍历物品数
        for (int i = 1; i <= n; i++) {
            // 每件物品有个单独的价值组(集合)
            for (int j = 1; j <= K; j++) {
                for (int k = j; k <= target; k++) {
                    // 由上一件物品转化来
                    dp[i][k] += dp[i-1][k - j];
                    dp[i][k] %= mod;
                }
            }
        }

        return dp[n][target];
    }
};

🏷️1449. 数位成本和为目标值的最大数字

⭐求具体方案 + 完全背包

题意与要求

本题的题面非常绕，这里就不解释了

求解具体方案，核心思想是逆向寻路

若dp时为顺序，则求解时为逆序

一般是从满状态返回，根据是否能够松弛操作的过程倒推

然后状态值不断减去容量

Code

class Solution {
public:
    string largestNumber(vector<int>& cost, int target) {
        // 本题为定值9
        int n = cost.size();
        vector<int> dp(target + 1, INT_MIN);
        dp[0] = 0;

        for (int i = 0; i < n; i++) {
            // 完全背包
            for (int j = cost[i]; j <= target; j++) {
                dp[j] = max(dp[j], dp[j - cost[i]] + 1);
            }
        }

        if (dp[target] < 0) {
            return "0";
        }

        string s;
        // 与上方的i循环的遍历方向相反
        // 满容量，逆向倒推
        // 本题这里正好，路径的值是按照字典序的逆序
        for (int i = n - 1, vol = target; i >= 0; i--) {
            for (int j = cost[i]; vol >= j && dp[vol] == dp[vol - j] + 1; vol -= j) {
                s += '1' + i;
            }
        }

        return s;
    }
};

🏷️1774. 最接近目标价格的甜点成本

⭐价值==容量求bool状态

题意与思路

在一个给定基数的情况下，添加物品，判断总量和target的比较，求差值最小的状态

Code

官方写法借助了很多技巧

下面是我个人的写法

class Solution {
public:
    int closestCost(vector<int>& baseCosts, vector<int>& toppingCosts, int target) {
        int ans = baseCosts[0];

        auto getMax = [&](int cmp) {
            int diff1 = abs(target - ans);
            int diff2 = abs(target - cmp);
            if (diff1 < diff2) {
                ans = ans;
            } else if (diff1 > diff2) {
                ans = cmp;
            } else {
                ans = min(ans, cmp);
            }
        };

        for (int base : baseCosts) {
            getMax(base);
            // 直接超过上限，break
            if (base >= target) {
                continue;
            }
            // 用余量进行背包dp
            int diff = target - base;
            // 一个坑，这个余量不一定是低于target的
            diff += abs(target - ans);

            // 两次01背包
            vector<int> dp(diff + 1);
            vector<bool> vis(diff + 1);
            vis[0] = true;
            for (int& top : toppingCosts) {
                for (int i = diff; i >= top; i += -1) {
                    if (vis[i - top]) {
                        dp[i] = max(dp[i], dp[i - top] + top);
                        vis[i] = true;
                    }
                }
                for (int i = diff; i >= top; i += -1) {
                    if (vis[i - top]) {
                        dp[i] = max(dp[i], dp[i - top] + top);
                        vis[i] = true;
                    }
                }
            }

            int val = *max_element(dp.begin(), dp.end());
            for (int i = 0; i <= diff; i += 1) {
                int val = base + dp[i];
                getMax(val);
            }
        }

        return ans;
    }
};

🏷️2218. 从栈中取出 K 个硬币的最大面值和

⭐分组背包

题意与要求

有多组物品，每组可以视为一个栈，总共取k次，每取一次对应的那个栈pop

求可取得的最大值

一个栈就是一个组，取一次就是一点容量

每个栈可以连续的从顶部取，正好对应一个递增的序列，先用前缀和处理

同一个组中前缀和的每个元素就是一件物品，且只能取一件，必须容斥

本题对空间的先后需要很敏感

二维好理解点，但是二维需要处理0件物品的前缀和

Code

class Solution {
public:
    int maxValueOfCoins(vector<vector<int>>& piles, int K) {
        // k就是次数，就是容量
        vector<int> dp(K + 1);

        // 计算每组的前缀和
        for (int i = 0; i < piles.size(); i++) {
            for (int j = 1; j < piles[i].size(); j++) {
                piles[i][j] += piles[i][j - 1];
            }
        }

        // 处理每组物品
        for (int i = 0; i < piles.size(); i++) {
            // 遍历空间，背包提供的空间
            // 01背包，压缩空间
            // 先遍历大空间，才能和小元素容斥
            for (int j = K; j >= 0; j--) {
                // 每组中的每件物品，{容量，价值}
                for (int k = 1; k <= piles[i].size(); k++) {
                    int num = piles[i][k - 1];
                    if (k <= j) {
                        dp[j] = max(dp[j], dp[j - k] + num);
                    }
                }                
            }
        }

        return dp[K];
    }
};

二维最大的好处就是不用管循环的顺逆

滚动数组实现二维

class Solution {
public:
    int maxValueOfCoins(vector<vector<int>>& piles, int K) {
        // k就是次数，就是容量
        vector<int> dp(K + 1);

        // 计算每组的前缀和
        for (int i = 0; i < piles.size(); i++) {
            for (int j = 1; j < piles[i].size(); j++) {
                piles[i][j] += piles[i][j - 1];
            }
        }

        // 处理每组物品
        for (int i = 0; i < piles.size(); i++) {
            // 滚动数组实现二维
            // 因为二维分离原理，后两循环顺逆无关
            auto pre = dp;
            // 遍历每个物品
            // for (int j = 1; j <= piles[i].size(); j++) {
            for (int j = piles[i].size(); j >= 1; j--) {
                int num = piles[i][j - 1];
                // 每组中的每件物品，{容量，价值}
                // for (int k = K; k >= j; k--) {
                for (int k = j; k <= K; k++) {
                    int tmp = max(pre[k], pre[k - j] + num);
                    dp[k] = max(dp[k], tmp);
                }                
            }
        }

        return dp[K];
    }
};

前言

🔖思路与技巧

题单

⭐判断能否正好装满背包 + 完全背包 + 优先遍历容量

题意与要求

Code

⭐选取数

题意与要求

Code

⭐选取数

题意与要求

Code

⭐方案数 + 完全背包 + 优先遍历空间

题意与要求

Code

⭐num既是容量又是价值

题意与要求

Code

⭐选取数 + 多维度

题意与要求

Code

⭐负数偏移

题意与要求

Code

⭐方案数

题意与要求

Code

⭐背包中的战斗机(完全理解)

题意与要求

Code

⭐num既是容量又是价值

题意与要求

Code

⭐方案数 + 分组背包

题意与要求

Code

⭐求具体方案 + 完全背包

题意与要求

Code

⭐价值==容量 求bool状态

题意与思路

Code

⭐分组背包

题意与要求

Code

END

⭐价值==容量求bool状态