leetcode 2915. 和为目标值的最长子序列的长度
题目如下

数据范围

本题就是典型的背包问题target就是容量,nums[i]就是第i个物品的重量。其实就是选最多的物品使得背包刚好装满。
令f(i,j)为当考虑到i - 1物品时刚好装到j重量的物品数。
当j >= nums[j]时 有f(i,j) = max(f(i - 1,j - nums[i - 1]) + 1,f(i - 1,j))
当j < nums[j]时 有f(i,j) = f(i - 1,j)
当i >= 0 j == 0时有f(i,j) = 0
而i ==0 j > 0时显然序列不存在 为了避免影响答案我们置为负无穷
所以我们可以写出代码
通过代码(未优化)
class Solution {
public:int lengthOfLongestSubsequence(vector<int>& nums, int target) {int n = nums.size();int ans = -1;vector<vector<int>> dp(n + 1,vector<int>(target + 1,INT_MIN));for(int i = 0;i <= n;i++){dp[i][0] = 0;}for(int i = 1;i <= n;i++){for(int j = 1;j <= target;j++){if(j - nums[i - 1] >= 0){dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - nums[i - 1]] + 1);}else{dp[i][j] = dp[i - 1][j];}}}return dp[n][target] > 0 ?dp[n][target] : -1;}
};

当然因为每一次对j的遍历只需要用到上一行的数据所以我们只需要用一维数组倒序遍历j即可(倒序是为了防止本应该用到的旧数据被覆盖)
利用滚动数组优化后移的代码
class Solution {
public:int lengthOfLongestSubsequence(vector<int>& nums, int target) {int n = nums.size();int ans = -1;vector<int> dp(target + 1, INT_MIN);dp[0] = 0;for (int i = 1; i <= n; i++) {for (int j = target; j >= nums[i - 1]; j--) {dp[j] = max(dp[j], dp[j - nums[i - 1]] + 1);}}return dp[target] > 0 ? dp[target] : -1;}
};

相关文章:
leetcode 2915. 和为目标值的最长子序列的长度
题目如下 数据范围 本题就是典型的背包问题target就是容量,nums[i]就是第i个物品的重量。其实就是选最多的物品使得背包刚好装满。 令f(i,j)为当考虑到i - 1物品时刚好装到j重量的物品数。 当j > nums[j]时 有f(i,j) max(f(i - 1,j - nums[i - 1]) 1,f(i -…...
【Vue】打包vue3+vite项目发布到github page的完整过程
文章目录 第一步:打包第二步:github仓库设置第三步:安装插件gh-pages第四步:两个配置第五步:上传github其他问题1. 路由2.待补充 参考文章: 环境: vue3vite windows11(使用终端即可&…...
Flutter编译问题记录
问题: 运行出现以下报错 Launching lib/main.dart on macOS in debug mode... Warning: CocoaPods not installed. Skipping pod install. CocoaPods is a package manager for iOS or macOS platform code. Without CocoaPods, plugins will not work on iOS or …...
poetry shell - 作为插件安装和使用
安装插件 安装完 poetry,想进入环境,执行 poetry shell 后会报错,是因为 poetry shell 在后面的版本中,是作为插件,需要额外安装。 poetry self add poetry-plugin-shell关于 poetry-plugin-shell github : https:/…...
UE5中的快捷键汇总
以下是Unreal Engine 5(UE5)中一些常用的快捷键大全,涵盖编辑器操作、视口导航、蓝图编辑等多个方面(会持续补充作为笔记存在): 通用快捷键 快捷键功能Ctrl S保存当前关卡Ctrl Shift S保存所有Ctrl Z撤销Ctrl C复制Ctrl V…...
2月14(信息差)
🌍杭州:全球数贸港核心区建设方案拟出台 争取国家支持杭州在网络游戏管理给予更多权限 🎄Kimi深夜炸场:满血版多模态o1级推理模型!OpenAI外全球首次!Jim Fan:同天两款国产o1绝对不是巧合&#x…...
ElementUI 的组件 Switch(开关)如何让文字显示在按钮上
效果图: 一、引入switch组件 给组件自定义一个类:tableScopeSwitch,设置开关的值和对应展示的文字(开为 1,并展示启用;关为 0,并展示禁用)。 <div class"tableScopeSwitch…...
Redis常用的五种数据结构详解
一、Redis 数据库介绍 Redis 是一种键值(Key-Value)数据库。相对于关系型数据库(比如 MySQL),Redis 也被叫作非关系型数据库。 像 MySQL 这样的关系型数据库,表的结构比较复杂,会包含很多字段&…...
stm32 CubeMx 实现SD卡/sd nand FATFS读写测试
文章目录 stm32 CubeMx 实现SD卡/SD nand FATFS读写测试 1. 前言 2. 环境介绍 2.1 软硬件说明 2.2 外设原理图 3. 工程搭建 3.1 CubeMx 配置 3.2 SDIO时钟配置说明 3.2 读写测试 3.2.1 添加读写测试代码 3.3 FATFS文件操作 3.3.1 修改读写测试代码 3.4 配置问题记…...
【Unity】 HTFramework框架(六十)Assistant助手(在Unity中接入DeepSeek等AI语言大模型)
更新日期:2025年2月14日。 Github源码:[点我获取源码] Gitee源码:[点我获取源码] 索引 Assistant助手安装Ollama使用Assistant(在编辑器中)打开Assistant配置Assistant使用Assistant处理Assistant回复的内容使用推理大…...
web自动化笔记(二)
文章目录 一、参数化测试1.pytest命令2.实现参数化测试3.填写地址测试4.生成Allure测试报告5.关键字驱动 二、案例1.实现后台登录1.1登录1.2.处理验证码1.3.封装识别验证码函数 2.通过cookie保持登录2.1给页面添加cookie2.2获取页面的cookie2.3自动化获取cookie 三、excel进行数…...
IIS部署netcore程序后,出现500.30错误解决方案之一
netcore程序部署到IIS后一直出现错误,访问首页后会跳转到登录页地址,然后看到如下错误 HTTP Error 500.30 - ANCM In-Process Start Failure Common solutions to this issue: The application failed to start The application started but then stopp…...
spring 学习(spring-Dl补充(注入不同类型的数据))
前言 在之前的案例,列举的最多的是注入 对象。本篇博客则是补充说我们不仅可以注入对象 还可以注入其他的数据类型包括基本数据类型,引用数据类型。 注入基本数据类型 常见的基本数据类型有:short char int long float double boolean …...
Docker Desktop之Nginx
安装Nginx 把这个复制 到docker 中执行 即可...
利用ffplay播放udp组播视频流
ffplay -fs -fflags nobuffer -flags low_delay -analyzeduration 0 -probesize 32 -framedrop -sync ext -strict experimental udp://224.1.1.1:5001 -fs : 全屏显示 -fflags nobuffer : 禁用输入缓冲(减少100-200ms缓冲延迟) -an…...
【教程】MySQL数据库学习笔记(七)——多表操作(持续更新)
写在前面: 如果文章对你有帮助,记得点赞关注加收藏一波,利于以后需要的时候复习,多谢支持! 【MySQL数据库学习】系列文章 第一章 《认识与环境搭建》 第二章 《数据类型》 第三章 《数据定义语言DDL》 第四章 《数据操…...
2025.2.14——1400
2025.2.14——1400 A 1400 B 1400 C 1400 D 1400 E 1400 F 1400 G 1400 H 1400 ------------------------------------------------ 思维排序/双指针/二分/队列匹配思维二分/位运算思维数学思维 A 一眼想到的是维护信息计数。维护两个信息同时用长的一半去找短的一半…...
DeepSeek教unity------MessagePack-04
Union 联合 MessagePack for C# 支持序列化接口类型和抽象类类型的对象。它的行为类似于 XmlInclude 或 ProtoInclude。在 MessagePack for C# 中,这些被称为Union。只有接口和抽象类可以被 Union 属性注解。需要唯一的联合键。 /******************************…...
Java异常体系深度解析:从Exception到Error
文章目录 前言一、Java异常体系概览ExceptionError 二、受检异常与非受检异常受检异常(Checked Exception)非受检异常(Unchecked Exception) 三、常见的Error类型四、异常处理机制try-catch-finally结构Throws关键字 五、自定义异…...
【linux】文件与目录命令 - ln
文章目录 1. 基本用法2. 常用参数3. 用法举例4. 注意事项 ln 命令用于在文件系统中创建硬链接或符号链接(软链接),是文件共享和路径引用的常用工具。 1. 基本用法 语法: ln [选项] 源文件 [目标文件/目标目录]功能: 创…...
Vue记事本应用实现教程
文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展:显示创建时间8. 功能扩展:记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...
【杂谈】-递归进化:人工智能的自我改进与监管挑战
递归进化:人工智能的自我改进与监管挑战 文章目录 递归进化:人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管?3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...
CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型
CVPR 2025 | MIMO:支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题:MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者:Yanyuan Chen, Dexuan Xu, Yu Hu…...
k8s从入门到放弃之Ingress七层负载
k8s从入门到放弃之Ingress七层负载 在Kubernetes(简称K8s)中,Ingress是一个API对象,它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress,你可…...
智能在线客服平台:数字化时代企业连接用户的 AI 中枢
随着互联网技术的飞速发展,消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁,不仅优化了客户体验,还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用,并…...
【AI学习】三、AI算法中的向量
在人工智能(AI)算法中,向量(Vector)是一种将现实世界中的数据(如图像、文本、音频等)转化为计算机可处理的数值型特征表示的工具。它是连接人类认知(如语义、视觉特征)与…...
中医有效性探讨
文章目录 西医是如何发展到以生物化学为药理基础的现代医学?传统医学奠基期(远古 - 17 世纪)近代医学转型期(17 世纪 - 19 世纪末)现代医学成熟期(20世纪至今) 中医的源远流长和一脉相承远古至…...
人机融合智能 | “人智交互”跨学科新领域
本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...
基于IDIG-GAN的小样本电机轴承故障诊断
目录 🔍 核心问题 一、IDIG-GAN模型原理 1. 整体架构 2. 核心创新点 (1) 梯度归一化(Gradient Normalization) (2) 判别器梯度间隙正则化(Discriminator Gradient Gap Regularization) (3) 自注意力机制(Self-Attention) 3. 完整损失函数 二…...
2025年渗透测试面试题总结-腾讯[实习]科恩实验室-安全工程师(题目+回答)
安全领域各种资源,学习文档,以及工具分享、前沿信息分享、POC、EXP分享。不定期分享各种好玩的项目及好用的工具,欢迎关注。 目录 腾讯[实习]科恩实验室-安全工程师 一、网络与协议 1. TCP三次握手 2. SYN扫描原理 3. HTTPS证书机制 二…...
