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

动态规划34:446. 等差数列划分 II - 子序列

动态规划解题步骤:

1.确定状态表示:dp[i]是什么

2.确定状态转移方程:dp[i]等于什么

3.初始化:确保状态转移方程不越界

4.确定填表顺序:根据状态转移方程即可确定填表顺序

5.确定返回值

题目链接:446. 等差数列划分 II - 子序列 - 力扣(LeetCode)

题解1(三层for循环):

1.状态表示:dp[i][j]表示以nums[i] nums[j]结尾的等差子序列个数

2.状态转移方程:dif=nums[j]-nums[i]

                            如果存在nums[k]=nums[i]-dif  0<=k<i  (可能存在多个nums[k],每个都要算)

                            dp[i][j]+=dp[k][i]+1

3.初始化:创建dp表时全部初始化为0

4.填表顺序:从上往下,从左往右哦,依次填写二维dp表

5.返回值:返回dp表中所有元素之和(理论上是上三角部分,但是由于下三角和对角线都为0,因此返回总和也没问题)

class Solution {
public:int numberOfArithmeticSlices(vector<int>& nums) {//dp[i][j]表示以nums[i] nums[j]结尾的等差子序列个数//dif=nums[j]-nums[i]//nums[k]=nums[i]-dif//如果存在nums[k] 0<=k<i//重复的nums[k]也算//dp[i][j]+=dp[k][i]+1size_t n=nums.size();//创建dp表vector<vector<int>> dp(n,vector<int>(n,0));//初始化//创建dp表时全部初始化为0//填表for(int j=2;j<n;++j){for(int i=1;i<j;++i){long long dif=(long long)nums[j]-nums[i];long long temp=nums[i]-dif;for(int k=0;k<i;++k){if(nums[k]==temp){   dp[i][j]+=dp[k][i]+1;}}}}//返回值:返回dp表之和,2处理为0int ans=0;for(auto row:dp){for(auto value:row){ans+=value;}}return ans;}};

题解2(使用hash表代替一层for循环):

在填dp表之前,先将所有nums值和其对应的下标填入hash表,对于重复的nums值存在多个下标,使用vector存储其下标。查找nums[k]时使用hash表查找,hash[nums[k]]返回存储下标的vector,再遍历一次vector得到所有的k,但是只有满足小于i的k才符合条件。

class Solution {
public:int numberOfArithmeticSlices(vector<int>& nums) {//dp[i][j]表示以nums[i] nums[j]结尾的等差子序列个数//dif=nums[j]-nums[i]//nums[k]=nums[i]-dif//如果存在nums[k] 0<=k<i//重复的nums[k]也算//dp[i][j]+=dp[k][i]+1size_t n=nums.size();//创建hash表:nums值和下标绑定//重复元素有多个下标,则使用数组存储unordered_map<long long,vector<int>> hash;for(int i=0;i<n;++i){hash[nums[i]].push_back(i);}//创建dp表vector<vector<int>> dp(n,vector<int>(n,0));//初始化//创建dp表时全部初始化为0//填表for(int j=2;j<n;++j){for(int i=1;i<j;++i){long long dif=(long long)nums[j]-nums[i];long long temp=nums[i]-dif;if(hash.count(temp)){for(auto k:hash[temp]){if(k<i)dp[i][j]+=dp[k][i]+1;}}}}//返回值:返回dp表之和,2处理为0int ans=0;for(auto row:dp){for(auto value:row){ans+=value;}}return ans;}};

相关文章:

动态规划34:446. 等差数列划分 II - 子序列

动态规划解题步骤&#xff1a; 1.确定状态表示&#xff1a;dp[i]是什么 2.确定状态转移方程&#xff1a;dp[i]等于什么 3.初始化&#xff1a;确保状态转移方程不越界 4.确定填表顺序&#xff1a;根据状态转移方程即可确定填表顺序 5.确定返回值 题目链接&#xff1a;446.…...

PPT画图——如何设置导致图片为600dpi

winr&#xff0c;输入regedit打开注册表 按路径找&#xff0c;HKEY_CURRENT_USER\Software\Microsoft\Office\XX.0\PowerPoint\Options&#xff08;xx为版本号&#xff0c;16.0 or 15.0或则其他&#xff09;。名称命名&#xff1a;ExportBitmapResolution 保存即可&#xff0c;…...

【模块系列】STM321.69TFT屏幕

前言 在翻翻自己的器件盒的时候&#xff0c;发现这块好久之前买的TFT屏了&#xff0c;想起还没有用STM32点亮过&#xff0c;手头上正好有立创的梁山派STM32F4&#xff0c;就试着按照网上的文章教程顺便移植个LVGL看看&#xff0c;然后就有了就本文。 代码工程命名的是LvglDemo&…...

大模型辅助测试的正确打开方式?

测试的基本目的之一&#xff0c;是对被测对象进行质量评估。换言之&#xff0c;是要提供关于被测对象质量的“确定性”。因此&#xff0c;我们很忌讳在测试设计中引入“不确定性”&#xff0c;比如采用不可靠的测试工具、自动化测试代码逻辑复杂易错、测试选择假设过于主观等等…...

三相电的相电压、线电压、额定值、有效值,变比,零序电压,零序电流,三相三线制的三角形连接,三相四线制的星形连接

在二次设备配置中经常有根电压系统相关的名词&#xff0c;本身不是学电气的&#xff0c;有些名词经常查了忘&#xff0c;后续工作所有遇到跟电气相关的知识总结在此帖&#xff0c;便于后续直接查看&#xff0c;避免每次都要重新查、重新梳理。 相电压和线电压的关系是根号3倍&a…...

电商网站的基础用户数在100万,日活跃用户数在1万左右,系统下单TPS最大支持1000,应用服务要保证高可用。请预估该网站每天的使用成本。

要预估一个电商网站每天的使用成本&#xff0c;我们需要考虑多个因素&#xff0c;包括计算资源、数据库、缓存、存储、网络流量、负载均衡、安全服务、监控与日志等。以下是基于您提供的信息&#xff08;基础用户数100万&#xff0c;日活跃用户数1万&#xff0c;系统下单TPS最大…...

线性代数期末总复习的点点滴滴(1)

一、可逆矩阵、行列式、秩的关系 1.行列式与可逆矩阵的关系 所以&#xff0c;不难看出矩阵可逆的充分必要条件是该矩阵的行列式不为0。 2.接着来看&#xff0c;满秩和矩阵行列式的关系 不难看出满秩和行列式不为0是等价的。 3.再来看&#xff0c;满秩和矩阵可逆的关系 说明了…...

python+reportlab创建PDF文件

目录 字体导入 画布写入 创建画布对象 写入文本内容 写入图片内容 新增页 画线 表格 保存 模板写入 创建模板对象 段落及样式 表格及样式 画框 图片 页眉页脚 添加图形 构建pdf文件 reportlab库支持创建包含文本、图像、图形和表格的复杂PDF文档。 安装&…...

2024最新qrcode.min.js生成二维码Demo

找了一堆代码一堆GPT&#xff0c;终于给写对了&#xff1a; <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><…...

【Microi吾码】开源力量赋能低代码创新,重塑软件开发生态格局

我的个人主页 文章专栏&#xff1a;Microi吾码 一、引言 在当今数字化浪潮汹涌澎湃的时代&#xff0c;软件开发的需求呈现出爆发式增长。企业为了在激烈的市场竞争中脱颖而出&#xff0c;不断寻求创新的解决方案以加速数字化转型。传统的软件开发方式往往面临着开发周期长、技…...

Github - 如何提交一个带有“verified”标识的commit

Github - 如何提交一个带有“verified”标识的commit 前言(Why) 今天在Github上浏览某项目的commit记录的时候发现&#xff0c;有的commit记录带有verified绿色标识&#xff0c;有的带有橘色的Unverified标识&#xff0c;还有的什么都不显示。 既然我是根正苗红的作者(bushi)…...

HCIA笔记9--NAT、ACL与链路聚合

1. ACL ACL: 访问控制列表, Access Control List。 通过定义规则来允许或拒绝流量的通过。 1.1 ACL分类 1.2 配置实例 如图所示&#xff0c;对R2的访问只允许192.168.1.0/24网段。 我们可以配置基本acl来限制 acl 2000 acl number 2000 rule 5 permit source 192.168.1.0 0…...

SCSA:探索空间与通道注意力之间的协同效应

文章目录 摘要1 引言2 相关工作2.1 多语义空间信息2.2 注意力分解 3 方法3.1 共享多语义空间注意力&#xff1a;空间与通道分解3.2 渐进式通道自注意力3.3 协同效应3.4 注意力机制的整合 4 实验4.1 实验设置4.2 图像分类4.3 目标检测4.4 分割4.5 消融研究 5 可视化与分析5.1 注…...

深度学习助力股市预测:LSTM、RNN和CNN模型实战解析

作者&#xff1a;老余捞鱼 原创不易&#xff0c;转载请标明出处及原作者。 写在前面的话&#xff1a;众所周知&#xff0c;传统的股票预测模型有着各种各样的局限性。但在我的最新研究中&#xff0c;探索了一些方法来高效预测股市走势&#xff0c;即CNN、RNN和LSTM这些深度学习…...

组件库TDesign的表格<t-table>的使用,行列合并以及嵌入插槽实现图标展示,附踩坑

碎碎念&#xff1a;有点难用&#xff0c;不丝滑&#xff08;以下介绍的难点不是真的难&#xff0c;只是有点点点难用&#xff09; 背景&#xff1a;需要实现表格的行列合并以及图标的嵌入&#xff0c;想到使用组件库组件来方便开发 链接&#xff1a;TDesign Web Vue Next 难点…...

jwt在express中token的加密解密实现方法

在我们前面学习了 JWT认证机制在Node.js中的详细阐述 之后&#xff0c;今天来详细学习一下token是如何生成的&#xff0c;secret密钥的加密解密过程是怎么样的。 安装依赖 express&#xff1a;用于创建服务器jsonwebtoken&#xff1a;用于生成和验证JWTbody-parser&#xff1…...

结构体、共用体的字节对齐

结构体 结构体嵌套时&#xff1a;先算一下嵌套的结构体大小 嵌套进来的结构体大小为16字节&#xff0c;仍然进行&#xff0c;8字节对齐 typedef struct {char name[20];//20字节//000开始 20字节 019 struct{int day; //000开始 4字节 003char swx; //004开始 1…...

【YOLOv3】源码(train.py)

概述 主要模块分析 参数解析与初始化 功能&#xff1a;解析命令行参数&#xff0c;设置训练配置项目经理制定详细的施工计划和资源分配日志记录与监控 功能&#xff1a;初始化日志记录器&#xff0c;配置监控系统项目经理使用监控和记录工具&#xff0c;实时跟踪施工进度和质量…...

帧缓存的分配

帧缓存实际上就是一块内存。在 Android 系统中分配与回收帧缓存&#xff0c;使用的是一个叫 ION 的内核模块&#xff0c;App 使用 ioctl 系统调用后&#xff0c;会在内核内存中分配一块符合要求的内存&#xff0c;用户态会拿到一个 fd&#xff08;有的地方也称之为 handle&…...

基于顺序表实现队列循环队列的处理

文章目录 1.假溢出的现象2.循环队列3.顺序表实现队列架构4.顺序表模拟实现队列5.设计循环队列&#xff08;校招难度&#xff09; 1.假溢出的现象 下面的这个就是我们的假溢出的这个现象的基本的来源&#xff1a; 我们的这个队列里面是有9个位置的&#xff0c;我们知道这个队列…...

深度学习在微纳光子学中的应用

深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向&#xff1a; 逆向设计 通过神经网络快速预测微纳结构的光学响应&#xff0c;替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...

树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频

使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...

Xshell远程连接Kali(默认 | 私钥)Note版

前言:xshell远程连接&#xff0c;私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...

centos 7 部署awstats 网站访问检测

一、基础环境准备&#xff08;两种安装方式都要做&#xff09; bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats&#xff0…...

MMaDA: Multimodal Large Diffusion Language Models

CODE &#xff1a; https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA&#xff0c;它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构&#xf…...

【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表

1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...

linux 错误码总结

1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1

每日一言 生活的美好&#xff0c;总是藏在那些你咬牙坚持的日子里。 硬件&#xff1a;OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写&#xff0c;"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...

04-初识css

一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序

一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...