当前位置: 首页 > 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;我们知道这个队列…...

免费开源Sunshine游戏串流服务器终极指南:打造你的专属云游戏平台

免费开源Sunshine游戏串流服务器终极指南&#xff1a;打造你的专属云游戏平台 【免费下载链接】Sunshine Self-hosted game stream host for Moonlight. 项目地址: https://gitcode.com/GitHub_Trending/su/Sunshine 想要在任何设备上畅玩PC游戏&#xff0c;却受限于硬件…...

Kindle漫画转换终极方案:如何解决电子阅读器上的格式兼容性问题

Kindle漫画转换终极方案&#xff1a;如何解决电子阅读器上的格式兼容性问题 【免费下载链接】kcc KCC (a.k.a. Kindle Comic Converter) is a comic and manga converter for ebook readers. 项目地址: https://gitcode.com/gh_mirrors/kc/kcc 你是否曾经尝试在Kindle上…...

思源宋体免费商用字体:设计师的终极开源字体解决方案

思源宋体免费商用字体&#xff1a;设计师的终极开源字体解决方案 【免费下载链接】source-han-serif-ttf Source Han Serif TTF 项目地址: https://gitcode.com/gh_mirrors/so/source-han-serif-ttf 还在为商业项目寻找高质量中文字体而烦恼吗&#xff1f;Source Han Se…...

MagiskHide Props Config:设备属性管理的3大维度与安全检测绕过全指南

MagiskHide Props Config&#xff1a;设备属性管理的3大维度与安全检测绕过全指南 【免费下载链接】MagiskHidePropsConf This tool is now dead... 项目地址: https://gitcode.com/gh_mirrors/ma/MagiskHidePropsConf 一、价值定位&#xff1a;为什么每个root用户都需要…...

Python入门项目:用10行代码调用MogFace-large实现人脸检测

Python入门项目&#xff1a;用10行代码调用MogFace-large实现人脸检测 想学Python&#xff0c;但觉得枯燥的理论和语法让人昏昏欲睡&#xff1f;今天咱们换个玩法&#xff0c;直接上手一个能“看得见摸得着”的实战项目。想象一下&#xff0c;你只需要写10行左右的代码&#x…...

爱毕业aibiye等8款智能应用显著改善了论文撰写体验,编程与学术研究流程更加顺畅

文章总结表格&#xff08;工具排名对比&#xff09; 工具名称 核心优势 aibiye 精准降AIGC率检测&#xff0c;适配知网/维普等平台 aicheck 专注文本AI痕迹识别&#xff0c;优化人类表达风格 askpaper 快速降AI痕迹&#xff0c;保留学术规范 秒篇 高效处理混AIGC内容&…...

CefFlashBrowser:终极Flash浏览器解决方案,轻松玩转经典Flash游戏与课件

CefFlashBrowser&#xff1a;终极Flash浏览器解决方案&#xff0c;轻松玩转经典Flash游戏与课件 【免费下载链接】CefFlashBrowser Flash浏览器 / Flash Browser 项目地址: https://gitcode.com/gh_mirrors/ce/CefFlashBrowser 你是否还在为无法打开珍藏的Flash游戏而烦…...

Kubernetes 环境下 SkyWalking 的高效部署与性能调优

1. Kubernetes 环境下的 SkyWalking 部署实战 第一次在 Kubernetes 上部署 SkyWalking 时&#xff0c;我踩了不少坑。记得当时为了调试一个存储配置问题&#xff0c;整整熬了两个通宵。现在回想起来&#xff0c;如果当时有人能给我一份详细的实战指南&#xff0c;至少能节省 80…...

东华OJ-基础题-48-数列1(C++)

问题描述 思维的严密性是相当重要的&#xff0c;尤其是在程序设计中&#xff0c;一个小小的错误&#xff0c;就可能导致无法想象的后果。明明的爸爸是一名富有经验的程序设计专家&#xff0c;深知思维严密的重要性。于是在明明很小的时候&#xff0c;就通过游戏的方式训练明明的…...

STEP3-VL-10B实际作品集:MMBench 92.05分视觉识别能力高清图文输出示例

STEP3-VL-10B实际作品集&#xff1a;MMBench 92.05分视觉识别能力高清图文输出示例 1. 引言&#xff1a;当AI“看懂”了世界 你有没有想过&#xff0c;让AI像人一样“看懂”一张图片&#xff0c;到底有多难&#xff1f; 这不仅仅是识别出图片里有什么东西那么简单。比如给你…...