动态规划之二维背包及杂项

一和零

一和零

思路

• 状态表示：dp[i][j][k]表示，从前i个元素中选，字符0不超过j，字符1不超过k，所有选法中，最大的长度；
• 状态转移方程：根据第i个位置的状态来分析，我们令第i个元素中0的个数为a，1的个数为b
  • 不选第i个元素，则dp[i - 1][j][k]
  • 选第i个元素，则dp[i - 1][j - a][k - b] + 1(但此时需要特判，即j >= a, k >= b)
• 初始化：因为j, k在填表时会特判，所以我们仅考虑i = 0，此时从0个元素中选，空集，所以为0
• 填表顺序：i从小到大即可；
• 返回值：dp[len][m][n]
  C++代码

class Solution 
{
public:int findMaxForm(vector<string>& strs, int m, int n) {int len = strs.size();vector<vector<vector<int>>> dp(len + 1, vector<vector<int>>((m + 1), vector<int>(n + 1)));for(int i = 1; i <= len; i++){// 0       1int a = 0, b = 0;for(auto s : strs[i - 1])if(s == '0') a++;else b++;for(int j = 0; j <= m; j++)for(int k = 0; k <= n; k++){dp[i][j][k] = dp[i - 1][j][k];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];}
};

盈利计划

题目：盈利计划

思路

• 状态表示：dp[i][j][k]表示，从前i个计划中选，总人数不超过j，总利润至少为k，一共有多少中选法；
• 状态转移方程：根据第i个位置的状态来分析，我们令第i个元素中0的个数为a，1的个数为b
  • 不选第i个计划，则dp[i - 1][j][k]
  • 选第i个计划，则dp[i - 1][j - g[i]][max(0, k - p[i])] (但此时需要特判，即j >= g[i])
• 初始化：没有任务时，利润为0在这种情况下，无论人数限制为多少，都能找到一个空集的方案。因此初始化dp[0][j][0] 为1，其中 0 <= j <= n
• 填表顺序：i从小到大即可；
• 返回值：dp[len][m][n]
  C++代码

class Solution 
{const int MOD = 1e9 + 7;
public:int profitableSchemes(int n, int m, vector<int>& group, vector<int>& profit) {int len = group.size();vector<vector<vector<int>>> dp(len + 1, vector<vector<int>>(n + 1, vector<int>(m + 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 <= m; 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][m];}
};

组合总和 Ⅳ

题目：组合总和 Ⅳ

思路

• 状态表示：dp[i]表示，总和为i 时，一共有多少种排列方案
• 状态转移方程：我们分析最后一个位置，选择数组中任意一个数nums[j]（0 <= j <= n - 1），我们就去剩下的位置找i - nums[j]（前提i >= nums[j]）；综上，dp[i] += dp[i - nums[j]]
• 初始化：dp[0]表示凑成0，此时只有空集一种方案，所以dp[0] = 1
• 填表顺序：从左往右
• 返回：dp[target]

C++代码

class Solution 
{
public:int combinationSum4(vector<int>& nums, int target) {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];}
};

不同的二叉搜索树

题目：不同的二叉搜索树

思路

• 状态转移：dp[i]表示，当结点数量为 i 个时，一共有多少颗BST
• 状态转移方程：选j位置的节点作为头结点，分析情况
  • j位置的左边坐标节点为[1, j - 1]。dp[j - 1]，结点数量为 j - 1个时，一共有多少颗BST
  • j位置的右边坐标节点为[j + 1, i]。dp[i - j]，结点数量为 i - j个时，一共有多少颗BST
  • 综上，dp[i] += dp[j - 1] * dp[i - j]；
• 初始化：dp[0] = 1此时表示没有节点的时候只有空树符合题意；
• 填表顺序：从左往右
• 返回值：dp[n]

C++代码

class Solution 
{
public:int numTrees(int n) {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];}
};