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];}
};