成都 网站开发ps做网页效果图

当前位置： 首页 > news >正文

成都 网站开发,ps做网页效果图,手机版网站建站,网站后台上图片后网页显示不正确算法沉淀——动态规划之其它背包问题与卡特兰数 二维费用的背包问题01.一和零02.盈利计划 似包非包组合总和 Ⅳ 卡特兰数不同的二叉搜索树 二维费用的背包问题 01.一和零 题目链接#xff1a;https://leetcode.cn/problems/ones-and-zeroes/ 给你一个二进制字符串数组 strs… 算法沉淀——动态规划之其它背包问题与卡特兰数 二维费用的背包问题01.一和零02.盈利计划 似包非包组合总和 Ⅳ 卡特兰数不同的二叉搜索树 二维费用的背包问题 01.一和零 题目链接https://leetcode.cn/problems/ones-and-zeroes/ 给你一个二进制字符串数组 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 。提示 1 strs.length 6001 strs[i].length 100strs[i] 仅由 0 和 1 组成1 m, n 100 思路 问题转化为二维费用的01背包问题 状态表示 dp[i][j][k] 表示从前 i 个字符串中挑选字符 0 的个数不超过 j字符 1 的个数不超过 k所有的选法中最大的长度。 状态转移方程 根据最后一步的状况分两种情况讨论 不选第 i 个字符串相当于去前 i - 1 个字符串中挑选并且字符 0 的个数不超过 j字符 1 的个数不超过 k。此时的最大长度为 dp[i][j][k] dp[i - 1][j][k]。选择第 i 个字符串接下来在前 i - 1 个字符串中挑选字符 0 的个数不超过 j - a字符 1 的个数不超过 k - b 的最大长度然后在这个长度后面加上字符串 i。此时 dp[i][j][k] dp[i - 1][j - a][k - b] 1。需要特判这种状态是否存在。 综上状态转移方程为dp[i][j][k] max(dp[i][j][k], dp[i - 1][j - a][k - b] 1)。 初始化 当没有字符串的时候没有长度因此初始化为 0。 填表顺序 保证第一维的循环从小到大即可。 返回值 根据状态表示返回 dp[l][m][n]。
代码 class Solution { public:int findMaxForm(vectorstring strs, int m, int n) {int lstrs.size();vectorvectorvectorint dp(l1,vectorvectorint(m1,vectorint(n1)));for(int i1;il;i){int a0,b0;for(char ch:strs[i-1])if(ch0) a;else b;for(int jm;j0;j–)for(int kn;k0;k–){dp[i][j][k]dp[i-1][j][k];if(jakb) dp[i][j][k]max(dp[i][j][k],dp[i-1][j-a][k-b]1);}}return dp[l][m][n];} };02.盈利计划 题目链接https://leetcode.cn/problems/profitable-schemes/ 集团里有 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) 。提示 1 n 1000 minProfit 1001 group.length 1001 group[i] 100profit.length group.length0 profit[i] 100 思路 状态表示 dp[i][j][k] 表示从前 i 个计划中挑选总人数不超过 j总利润至少为 k有多少种选法。 状态转移方程 根据最后一位的元素有两种选择策略 不选第 i 位置的计划此时只能在前 i - 1 个计划中挑选总人数不超过 j总利润至少为 k。此时有 dp[i - 1][j][k] 种选法。选择第 i 位置的计划在前 i - 1 个计划中挑选的限制变成了总人数不超过 j - g[i]总利润至少为 max(0, k - p[i])。此时有 dp[i - 1][j - g[i]][max(0, k - p[i])] 种选法。 注意特殊情况 如果 j - g[i] 0说明人数过多状态不合法舍去。对于 k - p[i] 0说明利润太高但问题要求至少为 k因此将其取 max(0, k - p[i])。 综上状态转移方程为dp[i][j][k] dp[i - 1][j][k] dp[i - 1][j - g[i]][max(0, k - p[i])]。 初始化 当没有任务时利润为 0。在这种情况下无论人数限制为多少都能找到一个「空集」的方案。因此初始化 dp[0][j][0] 为 1其中 0 j n。 填表顺序 根据状态转移方程保证 i 从小到大即可。 返回值 根据状态表示返回 dp[l][m][n]其中 l 表示计划数组的长度。
代码 class Solution {const int MOD1e97; public:int profitableSchemes(int n, int m, vectorint group, vectorint profit) {int l group.size();vectorvectorvectorint dp(l1,vectorvectorint(n1,vectorint(m1)));for(int j0;jn;j) dp[0][j][0]1;for(int i1;il;i)for(int j0;jn;j)for(int k0;km;k){dp[i][j][k]dp[i-1][j][k];if(jgroup[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[l][n][m];}
};似包非包 组合总和 Ⅳ 题目链接https://leetcode.cn/problems/combination-sum-iv/ 给你一个由 不同 整数组成的数组 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提示 1 nums.length 2001 nums[i] 1000nums 中的所有元素 互不相同1 target 1000 思路 注意这里题目意思容易混淆概念其实这里是一个排列问题而并非组合问题所以应该是普通的动态规划问题 状态表示 dp[i] 表示总和为 i 时一共有多少种排列方案。 状态转移方程 对于 dp[i]根据最后一个位置划分选择数组中的任意一个数 nums[j]其中 0 j n - 1。当 nums[j] i 时排列数等于先找到 i - nums[j] 的方案数然后在每一个方案后面加上一个数字 nums[j]。因为有很多个 j 符合情况状态转移方程为dp[i] dp[i - nums[j]]其中 0 j n - 1。 初始化 当和为 0 时我们可以什么都不选即「空集」一种方案因此 dp[0] 1。 填表顺序 根据状态转移方程从左往右填表。 返回值 根据状态表示返回 dp[target] 的值。
代码 class Solution { public:int combinationSum4(vectorint nums, int target) {vectordouble dp(target1);dp[0]1;for(int i1;itarget;i)for(int x:nums)if(xi) dp[i]dp[i-x];return dp[target];} };卡特兰数 不同的二叉搜索树 题目链接https://leetcode.cn/problems/unique-binary-search-trees/ 给你一个整数 n 求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种返回满足题意的二叉搜索树的种数。 示例 1 输入n 3 输出5示例 2 输入n 1 输出1提示 1 n 19 思路 状态表示 dp[i] 表示当结点数量为 i 个时一共有多少颗 BST。 状态转移方程 对于 dp[i]选择每一个结点 j 作为头结点分析不同头结点的 BST 数量。根据 BST 的定义j 号结点的左子树的结点编号在 [1, j-1] 之间有 j-1 个结点右子树的结点编号在 [j1, i] 之间有 i-j 个结点。因此j 号结点作为头结点的 BST 种类数量为 dp[j-1] * dp[i-j]。综合每一个可能的头结点状态转移方程为dp[i] dp[j-1] * dp[i-j]其中 1 j i。 初始化 dp[0] 表示空树也是一颗二叉搜索树因此 dp[0] 1。针对 i 从 1 开始的情况需要通过 dp[j-1] * dp[i-j] 来计算。 填表顺序 从左往右填表保证每一步都有所依赖的子问题的解。 返回值 返回 dp[n] 的值表示结点数量为 n 时的 BST 种类数量。
代码 class Solution { public:int numTrees(int n) {vectorint dp(n1);dp[0]1;for(int i1;in;i)for(int j1;ji;j)dp[i]dp[j-1]*dp[i-j];return dp[n];} };