代码随想录算法训练营day43|动态规划part10

news/2024/12/17 17:05:15/

今天的是子序列问题,第二题难度不大,可以采用类似贪心的思路求解。第一题的思想比较新颖,注意dp[i]是以i为末尾元素的最长递增子序列,可以用两层循环,第二层循环遍历从0到i-1,通过不断更新dp[i]的值求解最长递增子序列,这里的思路很巧妙。

另外,第一题还可以用贪心的方法,要使子序列尽可能长,就要使每个子序列中的数尽可能小,若遇到更小的数就将其替换。可以写出如下代码:

 for(auto num:nums){auto it=ranges::lower_bound(res,num);if(it==res.end()) {res.push_back(num);}else *it=num;}return res.size();

第三题的思路和第一题类似,

   vector<vector<int>>dp(nums1.size(),vector<int>(nums2.size(),0));
//dp[i][j]表示以nums1[i],nums2[j]为末尾元素的最长子序列的长度,需要初始化为0
 if(nums1[i]==nums2[j]&&i>0&&j>0) dp[i][j]=dp[i-1][j-1]+1;

这行代码的意思是如果两个数列有数字相同,就在前面的基础上加1,因为两个数列是同步的。

这道题卡哥采用的是i-1,j-1的写法,我认为用i,j更容易理解,只是需要多一步初始化的过程同时要防止数组越界:

 for(int i=0;i<nums1.size();i++) if(nums1[i]==nums2[0])dp[i][0]=1;for(int j=0;j<nums2.size();j++) if(nums2[j]==nums1[0]) dp[0][j]=1;

先处理完第一行,再处理后面的。


http://www.ppmy.cn/news/1555904.html

相关文章

游戏引擎学习第52天

仓库 : https://gitee.com/mrxiao_com/2d_game 这节的内容相当多 回顾 在游戏中&#xff0c;实体被分为不同的类别&#xff1a;接近玩家的“高频实体”、距离较远并正在模拟的“低频实体”和不进行更新的“休眠实体”。这些实体会根据它们与玩家的距离进行处理&#xff0c;接…

在Spring Boot中的实现国际化(i18n)

1.什么是国际化&#xff08;i18n&#xff09;&#xff1f; 国际化&#xff08;Internationalization&#xff0c;简称i18n&#xff09;是指在软件应用中支持多种语言和文化的能力。通过国际化&#xff0c;应用可以根据用户的语言和地区设置&#xff0c;动态地显示不同的文本内…

android全局拖拽效果实现startDragAndDrop

有多种方式实现全角拖拽&#xff0c;我们基于系统标准的api startDragAndDrop 来做介绍 实现步骤&#xff1a; 一、应用的的拖拽 1.1 通过长按触发 holder.itemView.setOnLongClickListener(new View.OnLongClickListener() {Overridepublic boolean onLongClick(View v) {C…

【人工智能】基于Python的自然语言处理:深入实现文本相似度计算

解锁Python编程的无限可能:《奇妙的Python》带你漫游代码世界 文本相似度计算是自然语言处理(NLP)中的核心任务,广泛应用于搜索引擎、推荐系统、问答系统等领域。本文全面解析文本相似度计算的核心技术,使用Python中的spaCy和sentence-transformers库实现多种方法,包括基…

Volta——开箱即用的Node.js 版本管理工具

Volta volta 是一个较新的 Node.js 版本管理器&#xff0c;旨在简化 Node.js 和其他工具的安装和管理&#xff0c;在 2019 年出世&#xff0c;仍在积极开发中。Volta 采用了与 nvm 不同的方法&#xff1a;它不是管理 Node.js 的多个版本&#xff0c;而是管理项目及其依赖项。当…

西南大学硕士论文latex配置

1、settings文件配置 强制使用xelatex编译&#xff0c;使用浏览器浏览。 {"latex-workshop.latex.recipe.default": "latexmk (xelatex)","latex-workshop.latex.recipes": [{"name": "latexmk (xelatex)","tools&qu…

代理 IP 行业现状与未来趋势分析

随着互联网的飞速发展&#xff0c;代理 IP 行业在近年来逐渐兴起并成为网络技术领域中一个备受关注的细分行业。它在数据采集、网络营销、隐私保护等多个方面发挥着重要作用&#xff0c;其行业现状与未来发展趋势值得深入探讨。 目前&#xff0c;代理 IP 行业呈现出以下几个显著…

web 五子棋小游戏

效果图 源码 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>Gomoku</title><link rel&q…