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 [选项] 源文件 [目标文件/目标目录]功能: 创…...
【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型
摘要 拍照搜题系统采用“三层管道(多模态 OCR → 语义检索 → 答案渲染)、两级检索(倒排 BM25 向量 HNSW)并以大语言模型兜底”的整体框架: 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后,分别用…...
深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录
ASP.NET Core 是一个跨平台的开源框架,用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录,以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...
JVM垃圾回收机制全解析
Java虚拟机(JVM)中的垃圾收集器(Garbage Collector,简称GC)是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象,从而释放内存空间,避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...
Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务
通过akshare库,获取股票数据,并生成TabPFN这个模型 可以识别、处理的格式,写一个完整的预处理示例,并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务,进行预测并输…...
Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)
引言:为什么 Eureka 依然是存量系统的核心? 尽管 Nacos 等新注册中心崛起,但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制,是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...
【AI学习】三、AI算法中的向量
在人工智能(AI)算法中,向量(Vector)是一种将现实世界中的数据(如图像、文本、音频等)转化为计算机可处理的数值型特征表示的工具。它是连接人类认知(如语义、视觉特征)与…...
IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)
文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...
【JavaWeb】Docker项目部署
引言 之前学习了Linux操作系统的常见命令,在Linux上安装软件,以及如何在Linux上部署一个单体项目,大多数同学都会有相同的感受,那就是麻烦。 核心体现在三点: 命令太多了,记不住 软件安装包名字复杂&…...
python执行测试用例,allure报乱码且未成功生成报告
allure执行测试用例时显示乱码:‘allure’ �����ڲ����ⲿ���Ҳ���ǿ�&am…...
Mysql中select查询语句的执行过程
目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析(Parser) 2.4、执行sql 1. 预处理(Preprocessor) 2. 查询优化器(Optimizer) 3. 执行器…...
