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

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就是容量&#xff0c;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的完整过程

文章目录 第一步&#xff1a;打包第二步&#xff1a;github仓库设置第三步&#xff1a;安装插件gh-pages第四步&#xff1a;两个配置第五步&#xff1a;上传github其他问题1. 路由2.待补充 参考文章&#xff1a; 环境&#xff1a; vue3vite windows11&#xff08;使用终端即可&…...

Flutter编译问题记录

问题&#xff1a; 运行出现以下报错 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&#xff0c;想进入环境&#xff0c;执行 poetry shell 后会报错&#xff0c;是因为 poetry shell 在后面的版本中&#xff0c;是作为插件&#xff0c;需要额外安装。 poetry self add poetry-plugin-shell关于 poetry-plugin-shell github : https:/…...

UE5中的快捷键汇总

以下是Unreal Engine 5&#xff08;UE5&#xff09;中一些常用的快捷键大全&#xff0c;涵盖编辑器操作、视口导航、蓝图编辑等多个方面(会持续补充作为笔记存在)&#xff1a; 通用快捷键 快捷键功能Ctrl S保存当前关卡Ctrl Shift S保存所有Ctrl Z撤销Ctrl C复制Ctrl V…...

2月14(信息差)

&#x1f30d;杭州&#xff1a;全球数贸港核心区建设方案拟出台 争取国家支持杭州在网络游戏管理给予更多权限 &#x1f384;Kimi深夜炸场&#xff1a;满血版多模态o1级推理模型&#xff01;OpenAI外全球首次&#xff01;Jim Fan&#xff1a;同天两款国产o1绝对不是巧合&#x…...

ElementUI 的组件 Switch(开关)如何让文字显示在按钮上

效果图&#xff1a; 一、引入switch组件 给组件自定义一个类&#xff1a;tableScopeSwitch&#xff0c;设置开关的值和对应展示的文字&#xff08;开为 1&#xff0c;并展示启用&#xff1b;关为 0&#xff0c;并展示禁用&#xff09;。 <div class"tableScopeSwitch…...

Redis常用的五种数据结构详解

一、Redis 数据库介绍 Redis 是一种键值&#xff08;Key-Value&#xff09;数据库。相对于关系型数据库&#xff08;比如 MySQL&#xff09;&#xff0c;Redis 也被叫作非关系型数据库。 像 MySQL 这样的关系型数据库&#xff0c;表的结构比较复杂&#xff0c;会包含很多字段&…...

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语言大模型)

更新日期&#xff1a;2025年2月14日。 Github源码&#xff1a;[点我获取源码] Gitee源码&#xff1a;[点我获取源码] 索引 Assistant助手安装Ollama使用Assistant&#xff08;在编辑器中&#xff09;打开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后一直出现错误&#xff0c;访问首页后会跳转到登录页地址&#xff0c;然后看到如下错误 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补充(注入不同类型的数据))

前言 在之前的案例&#xff0c;列举的最多的是注入 对象。本篇博客则是补充说我们不仅可以注入对象 还可以注入其他的数据类型包括基本数据类型&#xff0c;引用数据类型。 注入基本数据类型 常见的基本数据类型有&#xff1a;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 &#xff1a; 禁用输入缓冲&#xff08;减少100-200ms缓冲延迟&#xff09; -an…...

【教程】MySQL数据库学习笔记(七)——多表操作(持续更新)

写在前面&#xff1a; 如果文章对你有帮助&#xff0c;记得点赞关注加收藏一波&#xff0c;利于以后需要的时候复习&#xff0c;多谢支持&#xff01; 【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# 中&#xff0c;这些被称为Union。只有接口和抽象类可以被 Union 属性注解。需要唯一的联合键。 /******************************…...

Java异常体系深度解析:从Exception到Error

文章目录 前言一、Java异常体系概览ExceptionError 二、受检异常与非受检异常受检异常&#xff08;Checked Exception&#xff09;非受检异常&#xff08;Unchecked Exception&#xff09; 三、常见的Error类型四、异常处理机制try-catch-finally结构Throws关键字 五、自定义异…...

【linux】文件与目录命令 - ln

文章目录 1. 基本用法2. 常用参数3. 用法举例4. 注意事项 ln 命令用于在文件系统中创建硬链接或符号链接&#xff08;软链接&#xff09;&#xff0c;是文件共享和路径引用的常用工具。 1. 基本用法 语法&#xff1a; ln [选项] 源文件 [目标文件/目标目录]功能&#xff1a; 创…...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析

今天聊的内容&#xff0c;我认为是AI开发里面非常重要的内容。它在AI开发里无处不在&#xff0c;当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗"&#xff0c;或者让翻译模型 "将这段合同翻译成商务日语" 时&#xff0c;输入的这句话就是 Prompt。…...

简易版抽奖活动的设计技术方案

1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...

在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能

下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能&#xff0c;包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...

大型活动交通拥堵治理的视觉算法应用

大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动&#xff08;如演唱会、马拉松赛事、高考中考等&#xff09;期间&#xff0c;城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例&#xff0c;暖城商圈曾因观众集中离场导致周边…...

c++ 面试题(1)-----深度优先搜索(DFS)实现

操作系统&#xff1a;ubuntu22.04 IDE:Visual Studio Code 编程语言&#xff1a;C11 题目描述 地上有一个 m 行 n 列的方格&#xff0c;从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子&#xff0c;但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...

OkHttp 中实现断点续传 demo

在 OkHttp 中实现断点续传主要通过以下步骤完成&#xff0c;核心是利用 HTTP 协议的 Range 请求头指定下载范围&#xff1a; 实现原理 Range 请求头&#xff1a;向服务器请求文件的特定字节范围&#xff08;如 Range: bytes1024-&#xff09; 本地文件记录&#xff1a;保存已…...

Axios请求超时重发机制

Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式&#xff1a; 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要&#xff1a; 近期&#xff0c;在使用较新版本的OpenSSH客户端连接老旧SSH服务器时&#xff0c;会遇到 "no matching key exchange method found"​, "n…...

JavaScript 数据类型详解

JavaScript 数据类型详解 JavaScript 数据类型分为 原始类型&#xff08;Primitive&#xff09; 和 对象类型&#xff08;Object&#xff09; 两大类&#xff0c;共 8 种&#xff08;ES11&#xff09;&#xff1a; 一、原始类型&#xff08;7种&#xff09; 1. undefined 定…...

C++课设:简易日历程序(支持传统节假日 + 二十四节气 + 个人纪念日管理)

名人说:路漫漫其修远兮,吾将上下而求索。—— 屈原《离骚》 创作者:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 专栏介绍:《编程项目实战》 目录 一、为什么要开发一个日历程序?1. 深入理解时间算法2. 练习面向对象设计3. 学习数据结构应用二、核心算法深度解析…...