目录
leetcode 474.一和零
leetcode 879.盈利计划
leetcode 377.组合总和IV
leetcode 96.不同的二叉搜索树
今天，我们将通过 4 道题目，来带各位了解并掌握动态规划中的二维费用的背包问题、似包非包、卡特兰数
（下文中的标题都是leedcode对应题目的链接）
leetcode 474.一和零
我们先来解释一下题意，有一个strs数组，里面有很多由01组成的二进制元素，我们要做的就是找出里面所有的在规定数量内的01元素
但其实我们再细看的话，会发现这就是一道简单的01背包问题，因为对于每一个位置而言，我们还是选或者不选，只不过不一样的是，我们这一次需要对元素内部进行一次循环，也就是，我们用dp做的话，一共需要三层循环才能解决这道问题
我们的状态表示就是：在 i 位置以前的所有元素中，0 不超过 j 个，1 不超过 k 个的最多元素的数量
可以看到，我们这里面一共涉及了三个变量，相应的，我们的dp表就需要建三维，也就是dp[i][j][k]
来推导状态表示方程，我们当前位置元素的 0 要想不超过 j 个，那么首先我们需要遍历这个string以得知里面 0 和 1 的数量，假设 0 有 a 个，1 有 b 个，然后我们就应该去 j - a 位置去找，相应的 1 就应该去 k - b 位置去找，因为我们想不超过 j 个的话，当前有 a 个，j - a 就代表了剩余多少个 0，1 的情况同理
讲完这个之后，我们选的情况就讲完了，状态表示方程就是 dp[i-1][j-a][k-b]
除了选之外，我们还有不选的情况，既然不选，那么直接去 dp[i-1][j][k] 位置去找即可
然后，我们选的情况还需要判断条件才行，因为如果要求不超过10个1个9个0，但是这一个位置里面就有100个1和100个0，就直接超了，这种情况直接不考虑，所以就需要判断：
if(j >= a && k >= b)
最后，我们要的是可以选到的元素最多的情况，所以在这两个选法之中我们还需要加上一个max的逻辑
最后是初始化和返回值
首先是初始化，我们为了不越界，我们需要在数组外面多开一圈的空间，带入到二维里面的话就是这样的：
然后就是初始化，首先因为有判断条件，所以 j 和 k 是绝对不会越界的，所以我们的 j 和 k 位置可以直接从 0 开始初始化，至于 i 位置，这种情况就是：数组里面没有元素，但是需要在 j 个 1 和 k 个 0 之内的情况，我们没有元素，都能满足，但是值都是 0，因为我们没有元素可以选择
另外，vector 默认初始化为 0，这也就意味着我们其实不用初始化
最后是返回值，我们的状态表示是在 i 位置以前的所有元素中，0 不超过 j 个，1 不超过 k 个的最多元素的数量，所以我们的返回值就是dp[len][m][n]
代码如下：
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++){int a = 0, b = 0;for(auto e : strs[i-1])if(e == '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];}
};leetcode 879.盈利计划
经过上一题之后，相信各位一看到这道题目其实就已经知道大体的做题流程了
但是这道题其实还是有一点不一样的，主要就在利润那里
我们先来分析一下状态表示：在第 i 组之前的选法中，人数在 j 以内且利润至少为 k 的所有情况
接下来我们来推导一下状态表示方程：
首先我们在 i 位置的时候，有两种状态，一种是选当前位置，一种是不选
如果是不选的话，就直接是dp[i][j][k] = dp[i-1][j][k]
但如果是选的话，那么我们要想保证人数在 j 以内，当前人数有 group[i] 人，那么我们就应该去 dp[i-1][ j - group[i] ][ 暂且不填 ] 位置去找，然后为了保证 j - group[i] 的情况存在，所以我们需要判断一下 if(j >= group[i-1])
而 k 位置也是一样的......吗？其实不是的
因为我们要的是利润至少为 k，如果我现在的利润是100，要求利润至少为10，可不可以，当然可以，利润越多自然越好，但是我们10-100=-90，一个数组中自然不可能存在-90这样的位置，但是我们要的是有多少种选法，所以我们可以直接选取 0 位置的值做一个折中的策略，为什么呢，因为只要满足了至少这个条件，那么利润上面就没什么关系了，而 0 位置代表的是利润刚好为 k 的情况，那么这样利润就和-90的选取情况在这道题目中就是一样的情况了（别忘了人数的条件是不一定满足的）
那么我们的 k 是不用要求一定要大于 profit[i] 位置的，但是我们在状态表示的时候，我们需要做一个max判断，如果是负数坐标的话，那么就让这个坐标等于 0，如果不是的话那就直接是原坐标即可
而初始化也是多开一圈，而我们的第几组的人和利润是不需要考虑的，但是人数限制确实需要的，如果一个人没有，而且利润也规定为 0，那么无论我们的人数限制是多少，那么情况就都是 1，着一种情况就是都不选
代码如下：
class Solution {
public:int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {int MOD = 1e9+7;int len = group.size();vector<vector<vector<int>>> dp(len+1, vector<vector<int>>(n+1, vector<int>(minProfit+1)));for(int i = 0; i <= n; i++) dp[0][i][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];}
};空间优化后的代码如下:
class Solution {
public:int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {int MOD = 1e9+7;int len = group.size();vector<vector<int>> dp(n+1, vector<int>(minProfit+1));for(int i = 0; i <= n; i++) dp[i][0] = 1;for(int i = 1; i <= len; i++)for(int j = n; j >= group[i-1]; j--)for(int k = minProfit; k >= 0; k--){dp[j][k] += dp[j-group[i-1]][max(0, k-profit[i-1])];dp[j][k] %= MOD;}return dp[n][minProfit];}
};leetcode 377.组合总和IV
这一道题目看着像背包问题，但其实不是，因为如果是背包的话，那其实讲究的是组合，但是在这道题目里面，112和121是不同的情况，所以就不是背包
那么我们直接将他看作一道普通的线性dp即可
状态表示：在和为 i 的情况中，一共有多少种选法
状态表示方程：当我们到达 i 位置的时候，当前位置的值为nums[j]，那么我们要想刚好为 i，那么就应该去 i - nums[j] 位置去找，也就是直接加等即可
代码如下：
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(auto e : nums)if(i >= e) dp[i] += dp[i - e];return dp[target];}
};leetcode 96.不同的二叉搜索树
首先我们先来分析问题，问的是一共有多少种二叉树
那么我们假设有数组内元素为12345，那么对于 3 而言，左边有两种组成方式，右边也是有两种元素的组成数量，而这时候 n 为 5，那么在1~5之内，每一个元素都有当根节点的机会，所以我们应该有两层 for 循环，外层代表现在是0~i，里面层代表以哪一个值为根节点
而状态表示就是dp[i] = dp[j-1] * dp[ i - j ]
至于为什么是乘，因为假设左边两种，右边两种，左边两种为情况1和情况2，以此类推，右边是3和4，那么这时候直接自由组合，可以是（情况1、根、情况3），也可以是（1、4），（2、3）、（2、4），所以是乘法
代码如下：
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];}
};今天这篇博客到这里就结束啦~(￣▽￣)~*
如果觉得对你有帮助的话，希望可以关注一下喔