【动态规划】背包问题 - 二维费用的01背包问题

思路

1. 初始化数据：

   • len 是 strs 中字符串的数量。
   • dp[i][j][k] 表示在前 i 个字符串中，使用至多 j 个 ‘0’ 和 k 个 ‘1’ 能得到的最长子集长度。

2. 统计每个字符串的 ‘0’ 和 ‘1’ 数量：

   • 对于每个字符串，计算其包含的 ‘0’ 和 ‘1’ 数量，分别用 a 和 b 表示。

3. 动态规划状态转移：

   • 不选择当前字符串，dp[i][j][k] = dp[i-1][j][k]。
   • 如果可以选择当前字符串（即 j >= a 且 k >= b），则更新状态为 dp[i][j][k] = max(dp[i][j][k], dp[i-1][j-a][k-b] + 1)，这表示选择当前字符串后的最长子集长度。

4. 返回结果：

   • 最终结果为 dp[len][m][n]，即在所有字符串中，使用至多 m 个 ‘0’ 和 n 个 ‘1’ 能得到的最长子集长度。

这个算法通过三维 DP 表来处理每个子集的选择状态，确保在给定的 ‘0’ 和 ‘1’ 约束下，找到最大的子集长度。

代码

class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {int len = strs.size();// 创建dp数组// dp[i][j][k]: 在前i个数中选，0的个数不超过j，1的个数不超过k，时的最长子集长度vector<vector<vector<int>>> dp(len+1, vector<vector<int>>(m+1, vector<int>(n+1)));for(int i = 1; i <= len; ++i){int a = 0, b = 0; // 统计当前字符串的01个数for(char ch : strs[i-1]) // 下标映射if(ch == '1') b++;else a++;// 填表for(int j = 0; j <= m; ++j)for(int k = 0; k <= n; ++k){dp[i][j][k] = dp[i-1][j][k]; // 不选择i字符串if(j >= a && k >= b)dp[i][j][k] = max(dp[i][j][k], dp[i-1][j-a][k-b]+1);}}return dp[len][m][n];}
};

思路

1. 状态定义：

   • dp[i][j][k] 表示使用前 i 个计划，选用的员工人数不超过 j，总利润至少为 k 的方案数量。

2. 初始化：

   • dp[0][j][0] = 1 表示在没有选择任何计划的情况下，选择任意人数的员工，总利润可以被认为是0的情况有且仅有1种：即什么都不做。
   • 对于其他情况下，当选择0个计划时，所有人数的情况下利润都不能满足大于0的条件，所以这些状态也应初始化为0。

3. 状态转移：

   • 对于每个计划 i，考虑是否选择该计划：
     • 如果选择该计划，更新 dp[i][j][k]，将其设为 dp[i-1][j][k]（不选择该计划的方案数）加上选择该计划后的方案数。
     • 选择该计划后，员工人数减少 group[i-1]，利润减少 profit[i-1]。利润 k 需要用 max(0, k - profit[i-1]) 来避免负利润的情况。
   • 更新后的方案数需要对 MOD 取模，防止溢出。

4. 结果：

   • 最终的答案是 dp[len][n][minProfit]，即使用所有计划，员工人数不超过 n，利润至少为 minProfit 的方案数量。

复杂度分析

• 时间复杂度：O(len * n * minProfit)，其中 len 是计划数量，n 是员工数量，minProfit 是利润目标。
• 空间复杂度：O(len * n * minProfit)，需要一个三维的 DP 数组来存储状态。

代码

class Solution {
public:int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {const int MOD = 1e9 + 7;int len = group.size();// 创建dp数组// dp[i][j][k]: 在前i个计划中选择，人数不超过j，利润至少为k 的选法数量vector<vector<vector<int>>> dp(len+1, vector<vector<int>>(n+1, vector<int>(minProfit+1)));// 初始化元素for(int j = 0; j <= n; ++j) dp[0][j][0] = 1;// 填表for(int i = 1; i <= len; ++i)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 >= group[i-1]) // 下标映射dp[i][j][k] += dp[i-1][j-group[i-1]][max(0, k-profit[i-1])];dp[i][j][k] %= MOD;} return dp[len][n][minProfit];}
};

思路

1. 初始化数据：

   • n 是可用的总人数。
   • minProfit 是所需的最低利润。
   • group 和 profit 分别表示每个计划所需的人数和带来的利润。
   • MOD 是取模的常量，避免结果溢出。

2. 创建 DP 表：

   • dp[i][j][k] 表示在前 i 个计划中，选择方案使得使用的人数不超过 j，并且获得的利润至少为 k 的选法数量。

3. 初始化 DP 表：

   • dp[0][j][0] 初始化为 1，表示在没有任何计划时，无论人数 j 是多少，总是有 1 种方式（即选择什么都不做）。

4. 动态规划状态转移：

   • 不选择当前计划，dp[i][j][k] = dp[i-1][j][k]。
   • 如果选择当前计划（即 j >= group[i-1]），则从 dp[i-1][j-group[i-1]][max(0, k-profit[i-1])] 转移过来。这里的 max(0, k-profit[i-1]) 确保即使利润 k-profit[i-1] 小于零，也不会影响 DP 状态。

5. 取模操作：

   • 每次更新 dp 表时，都取模 MOD，确保结果不会因为大数而溢出。

6. 返回结果：

   • dp[len][n][minProfit] 表示在所有计划中，使用最多 n 人，并且获得至少 minProfit 利润的选法数量。

这段代码通过三维 DP 表来追踪不同计划、人数和利润条件下的方案数量，确保最终计算出符合条件的所有方案数。

代码

class Solution {
public:int jewelleryValue(vector<vector<int>>& frame) {int m = frame.size(), n = frame[0].size();// dp的创建 与 元素初始化vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));for(int i = 1; i <= m; ++i)for(int j = 1; j <= n; ++j)dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + frame[i-1][j-1]; // 映射下标（对于frame要-1）return dp[m][n];}
};

思路

1. 初始化 DP 数组：

   • dp[i] 表示拥有 i 个节点的二叉搜索树的数量。
   • dp[0] 初始化为 1，表示空树（即没有节点）视为一种有效的 BST。

2. 填充 DP 表：

   • 使用两层循环：
     • 外层循环遍历所有节点数 i 从 1 到 n。
     • 内层循环遍历每个节点 j 作为根节点时的情况，j 从 1 到 i。
     • 对于每个 j 作为根节点，左子树有 j-1 个节点，右子树有 i-j 个节点。因此，dp[i] 的更新公式是 dp[i] += dp[j-1] * dp[i-j]。

3. 返回结果：

   • dp[n] 就是拥有 n 个节点的所有可能的 BST 的数量。

代码

class Solution {
public:int numTrees(int n) {// 创建dp数组 dp[i]: 节点数为i时的二叉搜索树的种数vector<int> dp(n+1);// 初始化dp[0] = 1; // 空树算一种 / 为了后续填表正确// 填表for(int i = 1; i <= n; ++i)for(int j = 1; j <= i; ++j)dp[i] += dp[j-1] * dp[i-j];return dp[n];}
};

思路

1. 初始化 DP 数组：

   • vector<double> dp(target + 1); 创建了一个 DP 数组 dp，其中 dp[i] 表示和恰好为 i 的组合数。
   • dp[0] = 1; 初始化 dp[0] 为 1，这是因为和为 0 的唯一组合是空组合。

2. 动态规划填表：

   • 遍历所有的 i 从 1 到 target。
   • 对于每一个 i，遍历 nums 中的每个数 x。
     • 如果 i >= x，那么 i 这个目标值可以由 i-x 这个目标值加上 x 得到。即，dp[i] 可以从 dp[i - x] 递推过来。
     • 因此，dp[i] += dp[i - x]; 更新 dp[i] 的值。

3. 返回结果：

   • return dp[target]; 最终返回 dp[target]，即所有可能的组合数，使得选取的数的和为 target。

代码

class Solution {
public:int combinationSum4(vector<int>& nums, int target) {// 线性dp问题// 创建dp数组 dp[i]: 选择数使和恰好为i的组合总数vector<double> dp(target+1);dp[0] = 1; // 初始化for(int i = 1; i <= target; i++)for(int x : nums)if(i >= x)dp[i] += dp[i - x];return dp[target];}
};