C++--动态规划其他问题
1.一和零 力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
给你一个二进制字符串数组
strs和两个整数m和n。请你找出并返回
strs的最大子集的长度，该子集中 最多 有m个0和n个1。如果
x的所有元素也是y的元素，集合x是集合y的 子集 。示例 1：
输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3 输出：4 解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。 其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。示例 2：
输入：strs = ["10", "0", "1"], m = 1, n = 1 输出：2 解释：最大的子集是 {"0", "1"} ，所以答案是 2。
class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {int len=strs.size();vector<vector<int>> dp(m+1,vector<int>(n+1));for(int i=1;i<=len;i++){int a=0;int b=0;for(auto sh:strs[i-1]){if(sh=='0') a++;else b++;}for(int j=m;j>=0;j--){for(int k=n;k>=0;k--){dp[j][k]=dp[j][k];if(j>=a&&k-b>=0) dp[j][k]=max(dp[j][k],dp[j-a][k-b]+1);}}}return dp[m][n];}
};2.盈利计划 力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
集团里有
n名员工，他们可以完成各种各样的工作创造利润。第
i种工作会产生profit[i]的利润，它要求group[i]名成员共同参与。如果成员参与了其中一项工作，就不能参与另一项工作。工作的任何至少产生
minProfit利润的子集称为 盈利计划 。并且工作的成员总数最多为n。有多少种计划可以选择？因为答案很大，所以 返回结果模
10^9 + 7的值。示例 1：
输入：n = 5, minProfit = 3, group = [2,2], profit = [2,3] 输出：2 解释：至少产生 3 的利润，该集团可以完成工作 0 和工作 1 ，或仅完成工作 1 。 总的来说，有两种计划。示例 2：
输入：n = 10, minProfit = 5, group = [2,3,5], profit = [6,7,8] 输出：7 解释：至少产生 5 的利润，只要完成其中一种工作就行，所以该集团可以完成任何工作。 有 7 种可能的计划：(0)，(1)，(2)，(0,1)，(0,2)，(1,2)，以及 (0,1,2) 。
class Solution {const int MOD = 10 ^ 9 + 7;
public:int profitableSchemes(int n, int m, vector<int>& g, vector<int>& p){int len = g.size();vector<vector<int>> dp(n + 1, vector<int>(m + 1));for (int j = 0; j <= n; j++) dp[j][0] = 1;for (int i = 1; i <= len; i++){for (int j = n; j>=g[i-1]; j--){for (int k=m; k >=0; k--){dp[j][k] += dp[j - g[i - 1]][max(0, k - p[i - 1])];dp[j][k]%=1000000007;}}}return dp[n][m];}
};3.组合总和4 力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
给你一个由 不同 整数组成的数组
nums，和一个目标整数target。请你从nums中找出并返回总和为target的元素组合的个数。题目数据保证答案符合 32 位整数范围。
示例 1：
输入：nums = [1,2,3], target = 4 输出：7 解释： 所有可能的组合为： (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1) 请注意，顺序不同的序列被视作不同的组合。示例 2：
输入：nums = [9], target = 3 输出：0
class Solution {
public:int combinationSum4(vector<int>& nums, int target) {int n=nums.size();vector<double> dp(target+1);dp[0]=1;//初始化for(int i=1;i<=target;i++){for(int j=0;j<n;j++){if(i-nums[j]>=0)dp[i]+=dp[i-nums[j]];}}return dp[target];}
};4.不同的二叉搜索树 力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
给你一个整数
n，求恰由n个节点组成且节点值从1到n互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。示例 1：
输入：n = 3 输出：5示例 2：
输入：n = 1 输出：1
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];}
};