算法沉淀——动态规划之其它背包问题与卡特兰数(leetcode真题剖析)

news/2024/4/19 14:02:05/文章来源:https://blog.csdn.net/kingxzq/article/details/136508622

在这里插入图片描述

算法沉淀——动态规划之其它背包问题与卡特兰数

  • 二维费用的背包问题
    • 01.一和零
    • 02.盈利计划
  • 似包非包
    • 组合总和 Ⅳ
  • 卡特兰数
    • 不同的二叉搜索树

二维费用的背包问题

01.一和零

题目链接:https://leetcode.cn/problems/ones-and-zeroes/

给你一个二进制字符串数组 strs 和两个整数 mn

请你找出并返回 strs 的最大子集的长度,该子集中 最多m0n1

如果 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 <= 600
  • 1 <= strs[i].length <= 100
  • strs[i] 仅由 '0''1' 组成
  • 1 <= m, n <= 100

思路

问题转化为二维费用的01背包问题:

  1. 状态表示:
    • dp[i][j][k] 表示从前 i 个字符串中挑选,字符 0 的个数不超过 j,字符 1 的个数不超过 k,所有的选法中,最大的长度。
  2. 状态转移方程:
    • 根据最后一步的状况,分两种情况讨论:
      • 不选第 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)
  3. 初始化:
    • 当没有字符串的时候,没有长度,因此初始化为 0
  4. 填表顺序:
    • 保证第一维的循环从小到大即可。
  5. 返回值:
    • 根据状态表示,返回 dp[l][m][n]

代码

class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {int l=strs.size();vector<vector<vector<int>>> dp(l+1,vector<vector<int>>(m+1,vector<int>(n+1)));for(int i=1;i<=l;i++){int a=0,b=0;for(char ch:strs[i-1])if(ch=='0') a++;else b++;for(int j=m;j>=0;j--)for(int k=n;k>=0;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[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 <= 100
  • 0 <= minProfit <= 100
  • 1 <= group.length <= 100
  • 1 <= group[i] <= 100
  • profit.length == group.length
  • 0 <= profit[i] <= 100

思路

  1. 状态表示:
    • dp[i][j][k] 表示从前 i 个计划中挑选,总人数不超过 j,总利润至少为 k,有多少种选法。
  2. 状态转移方程:
    • 根据最后一位的元素,有两种选择策略:
      • 不选第 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])]
  3. 初始化:
    • 当没有任务时,利润为 0。在这种情况下,无论人数限制为多少,都能找到一个「空集」的方案。因此初始化 dp[0][j][0]1,其中 0 <= j <= n
  4. 填表顺序:
    • 根据状态转移方程,保证 i 从小到大即可。
  5. 返回值:
    • 根据状态表示,返回 dp[l][m][n],其中 l 表示计划数组的长度。

代码

class Solution {const int MOD=1e9+7;
public:int profitableSchemes(int n, int m, vector<int>& group, vector<int>& profit) {int l = group.size();vector<vector<vector<int>>> dp(l+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<=l;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[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 <= 200
  • 1 <= nums[i] <= 1000
  • nums 中的所有元素 互不相同
  • 1 <= target <= 1000

思路

注意这里题目意思容易混淆概念,其实这里是一个排列问题而并非组合问题,所以应该是普通的动态规划问题

  1. 状态表示:
    • dp[i] 表示总和为 i 时,一共有多少种排列方案。
  2. 状态转移方程:
    • 对于 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
  3. 初始化:
    • 当和为 0 时,我们可以什么都不选,即「空集」一种方案,因此 dp[0] = 1
  4. 填表顺序:
    • 根据状态转移方程,从左往右填表。
  5. 返回值:
    • 根据状态表示,返回 dp[target] 的值。

代码

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(x<=i) dp[i]+=dp[i-x];return dp[target];}
};

卡特兰数

不同的二叉搜索树

题目链接:https://leetcode.cn/problems/unique-binary-search-trees/

给你一个整数 n ,求恰由 n 个节点组成且节点值从 1n 互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。

示例 1:

输入:n = 3
输出:5

示例 2:

输入:n = 1
输出:1

提示:

  • 1 <= n <= 19

思路

  1. 状态表示:
    • dp[i] 表示当结点数量为 i 个时,一共有多少颗 BST。
  2. 状态转移方程:
    • 对于 dp[i],选择每一个结点 j 作为头结点,分析不同头结点的 BST 数量。
    • 根据 BST 的定义,j 号结点的左子树的结点编号在 [1, j-1] 之间,有 j-1 个结点,右子树的结点编号在 [j+1, i] 之间,有 i-j 个结点。
    • 因此,j 号结点作为头结点的 BST 种类数量为 dp[j-1] * dp[i-j]
    • 综合每一个可能的头结点,状态转移方程为:dp[i] += dp[j-1] * dp[i-j],其中 1 <= j <= i
  3. 初始化:
    • dp[0] 表示空树,也是一颗二叉搜索树,因此 dp[0] = 1
    • 针对 i 从 1 开始的情况,需要通过 dp[j-1] * dp[i-j] 来计算。
  4. 填表顺序:
    • 从左往右填表,保证每一步都有所依赖的子问题的解。
  5. 返回值:
    • 返回 dp[n] 的值,表示结点数量为 n 时的 BST 种类数量。

代码

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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_996817.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

论文阅读-高效构建检查点

论文标题&#xff1a;On Efficient Constructions of Checkpoints 摘要 高效构建检查点/快照是训练和诊断深度学习模型的关键工具。在本文中&#xff0c;我们提出了一种适用于检查点构建的有损压缩方案&#xff08;称为LC-Checkpoint&#xff09;。LC-Checkpoint同时最大化了…

使用 llama.cpp 在本地部署 AI 大模型的一次尝试

对于刚刚落下帷幕的2023年,人们曾经给予其高度评价——AIGC元年。随着 ChatGPT 的火爆出圈,大语言模型、AI 生成内容、多模态、提示词、量化…等等名词开始相继频频出现在人们的视野当中,而在这场足以引发第四次工业革命的技术浪潮里,人们对于人工智能的态度,正从一开始的…

LeetCode73题:矩阵置零(python3)

代码思路&#xff1a; 这里用矩阵的第一行和第一列来标记是否含有0的元素&#xff0c;但这样会导致原数组的第一行和第一列被修改&#xff0c;无法记录它们是否原本包含 0。因此我们需要额外使用两个标记变量分别记录第一行和第一列是否原本包含 0。 class Solution:def setZe…

STM32CubeMX学习笔记14 ---SPI总线

1. 简介 1.1 SPI总线介绍 SPI 是英语Serial Peripheral interface的缩写&#xff0c;顾名思义就是串行外围设备接口。是Motorola(摩托罗拉)首先在其MC68HCXX系列处理器上定义的。 SPI&#xff0c;是一种高速的&#xff0c;全双工&#xff0c;同步的通信总线&#xff0c;并且在…

前端实现一个绕圆心转动的功能

前言&#xff1a; 今天遇到了一个有意思的需求&#xff0c;如何实现一个元素绕某一个点来进行圆周运动&#xff0c;用到了一些初高中的数学知识&#xff0c;实现起来还是挺有趣的&#xff0c;特来分享&#x1f381;。 一. 效果展示 我们先展示效果&#xff0c;如下图所示&…

改进YOLO系列 | YOLOv5/v7 引入通用高效层聚合网络 GELAN | YOLOv9 新模块

今天的深度学习方法专注于如何设计最合适的目标函数,以使模型的预测结果最接近真实情况。同时,必须设计一个合适的架构,以便为预测提供足够的信息。现有方法忽视了一个事实,即当输入数据经过逐层特征提取和空间转换时,会丢失大量信息。本文将深入探讨数据通过深度网络传输…

视频编码中常用的测试YUV系列及说明

vcc最新规定的测试序列如下所示&#xff0c;对于RA和LD配置&#xff0c;所有序列的所有帧都需要测试&#xff0c;对于intra配置仅需测试前8帧。 每列含义如下&#xff1a; A1、A2测试序列在LD配置下编码时应编码帧数为帧率的三倍。 “M”表示在该配置下必须测试这条序列。 …

基于 LLaMA 和 LangChain 实践本地 AI 知识库

有时候,我难免不由地感慨,真实的人类世界,本就是一个巨大的娱乐圈,即使是在英雄辈出的 IT 行业。数日前,Google 正式对外发布了 Gemini 1.5 Pro,一个建立在 Transformer 和 MoE 架构上的多模态模型。可惜,这个被 Google 寄予厚望的产品并未激起多少水花,因为就在同一天…

根据标签出现的频次渲染不同大小的圆和文字,圆随机摆放且相互之间不重叠

效果图&#xff1a; 按每个标签出现的频次大小渲染出不同比例大小的圆&#xff0c;渲染的圆的宽度区间为 [40, 160] &#xff0c;其中的文字的大小区间为 [12, 30] &#xff0c;圆的位置随机摆放且不重叠。 根据已知条件可得出&#xff0c;标签中频次最高的对应圆的宽度(直径…

Mac Pro 突然不能双击打开文件夹

当Mac Pro 突然不能双击打开文件夹 不防右击看看这儿 有没有勾选 如果勾选就会在打开的瞬间 闪退关掉文件夹

如何恢复edge的自动翻译功能

介绍&#xff1a;对于英文不好的小伙伴&#xff0c;把英语翻译成中文是有帮助的&#xff0c;而edge可以直接对英文页面翻译这一功能更是受人喜爱&#xff0c;但是&#xff0c;最近发现这一项功能消失了。 原始界面&#xff1a; 下面展示如何恢复该功能。 1.打开edge&#xff…

docker自定义镜像与上传

alpine制作jdk镜像 alpine Linux简介 1.Alpine Linux是一个轻型Linux发行版&#xff0c;它不同于通常的Linux发行版&#xff0c;Alpine采用了musl libc 和 BusyBox以减少系统的体积和运行时的资源消耗。 2.Alpine Linux提供了自己的包管理工具&#xff1a;apk(注意&#xff1a;…

【nowcoder】NC248 左叶子之和

NC248 左叶子之和 计算给定二叉树的左叶子之和。 树上叶子节点指没有后继节点的节点&#xff0c;左叶子指连向父节点的左侧的叶子节点。 int sumOfLeftLeaves(struct TreeNode* root ) {if (root ! NULL) {int sum 0;if (root->left ! NULL && root->left->…

可观测性十大场景 | 关于保险行业开门红期间应用性能的端到端全栈可观测

【场景概述】 保险行业的“开门红”是每年10月份到次年2月份的业绩冲刺期&#xff0c;各大保险公司纷纷推出独具特色的理财产品&#xff0c;吸引广大客户的目光&#xff0c;以期在新年伊始便赢得“开门红”的吉祥兆头。这段时期&#xff0c;保险收入占比接近全年收入的50%&…

【UE 材质 Niagara】爆炸效果

目录 效果 步骤 一、材质部分 二、Niagara部分 效果 步骤 一、材质部分 1. 创建一个材质&#xff0c;这里命名为“M_Burst” 打开“M_Burst”&#xff0c;设置混合模式为半透明&#xff0c;设置着色模型为无光照&#xff0c;勾选双面显示 在材质图表中首先创建扰动效果 其…

CVPR 2024 | Modular Blind Video Quality Assessment:模块化无参视频质量评估

无参视频质量评估 (Blind Video Quality Assessment&#xff0c;BVQA) 在评估和改善各种视频平台并服务用户的观看体验方面发挥着关键作用。当前基于深度学习的模型主要以下采样/局部块采样的形式分析视频内容&#xff0c;而忽视了实际空域分辨率和时域帧率对视频质量的影响&am…

Vue.js+SpringBoot开发天然气工程运维系统

目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 系统角色分类2.2 核心功能2.2.1 流程 12.2.2 流程 22.3 各角色功能2.3.1 系统管理员功能2.3.2 用户服务部功能2.3.3 分公司&#xff08;施工单位&#xff09;功能2.3.3.1 技术员角色功能2.3.3.2 材料员角色功能 2.3.4 安…

[c++] 模板

c 中的模板通过将类型参数化&#xff0c;可以提高代码的复用性。模板并不能减少代码量&#xff0c;只是从开发者的角度来看&#xff0c;代码量减少了&#xff0c;复用性提高了&#xff1b;从二进制文件的角度看&#xff0c;代码量没有减小。 1 函数模板 当求两个数的和时&…

PowerBI怎么修改数据库密码

第一步&#xff1a;点击转换数据 第二步&#xff1a;点击数据源设置 第三步&#xff1a;点击编辑权限 第四步&#xff1a;点击编辑 第五步&#xff1a;输入正要修改的密码就可以了

分享几种简约大方的ListView外观设计(qml)

一、前言 最近才学到这里&#xff0c;感觉基础的 ListView 很丑&#xff0c;就现学现用弄个几个自认为还行的设计给大家献丑了。如果你觉得还不错&#xff0c;代码就在下面拿去直接用&#xff0c;顺便给我点个赞哈 ~ 感谢感谢 ~ 二、正文 设计1 第一种就是正常的左侧边栏&am…