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 [选项] 源文件 [目标文件/目标目录]功能: 创…...
Keil 中设置 STM32 Flash 和 RAM 地址详解
文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...
聊一聊接口测试的意义有哪些?
目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开,首…...
全志A40i android7.1 调试信息打印串口由uart0改为uart3
一,概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本:2014.07; Kernel版本:Linux-3.10; 二,Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01),并让boo…...
Spring AI与Spring Modulith核心技术解析
Spring AI核心架构解析 Spring AI(https://spring.io/projects/spring-ai)作为Spring生态中的AI集成框架,其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似,但特别为多语…...
ABAP设计模式之---“简单设计原则(Simple Design)”
“Simple Design”(简单设计)是软件开发中的一个重要理念,倡导以最简单的方式实现软件功能,以确保代码清晰易懂、易维护,并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计,遵循“让事情保…...
mac 安装homebrew (nvm 及git)
mac 安装nvm 及git 万恶之源 mac 安装这些东西离不开Xcode。及homebrew 一、先说安装git步骤 通用: 方法一:使用 Homebrew 安装 Git(推荐) 步骤如下:打开终端(Terminal.app) 1.安装 Homebrew…...
Python 实现 Web 静态服务器(HTTP 协议)
目录 一、在本地启动 HTTP 服务器1. Windows 下安装 node.js1)下载安装包2)配置环境变量3)安装镜像4)node.js 的常用命令 2. 安装 http-server 服务3. 使用 http-server 开启服务1)使用 http-server2)详解 …...
C语言中提供的第三方库之哈希表实现
一. 简介 前面一篇文章简单学习了C语言中第三方库(uthash库)提供对哈希表的操作,文章如下: C语言中提供的第三方库uthash常用接口-CSDN博客 本文简单学习一下第三方库 uthash库对哈希表的操作。 二. uthash库哈希表操作示例 u…...
深入浅出Diffusion模型:从原理到实践的全方位教程
I. 引言:生成式AI的黎明 – Diffusion模型是什么? 近年来,生成式人工智能(Generative AI)领域取得了爆炸性的进展,模型能够根据简单的文本提示创作出逼真的图像、连贯的文本,乃至更多令人惊叹的…...
ubuntu22.04有线网络无法连接,图标也没了
今天突然无法有线网络无法连接任何设备,并且图标都没了 错误案例 往上一顿搜索,试了很多博客都不行,比如 Ubuntu22.04右上角网络图标消失 最后解决的办法 下载网卡驱动,重新安装 操作步骤 查看自己网卡的型号 lspci | gre…...
