算法训练营day53_动态规划（3.17提前写）
创始人
2025-05-30 00:34:34

算法训练营day53_动态规划（3.17提前写）

1143.最长公共子序列

与最长公共子数组相比，多了俩转移情况；

class Solution {
public:int longestCommonSubsequence(string text1, string text2) {int n1=text1.size(),n2=text2.size();vector> f(n1+1,vector(n2+1,0));for(int i=1;i<=n1;i++){for(int j=1;j<=n2;j++){f[i][j]=max(f[i-1][j],f[i][j-1]);if(text1[i-1]==text2[j-1]) f[i][j]=max(f[i][j],f[i-1][j-1]+1);}}return f[n1][n2];      }
};

1035.不相交的线

a中与b中相同的数可以连接，又由于不能相交，所以相对顺序要一致，就是找A与B中相同的子序列，即公共子序列；

要求最大连接数，就是最长公共子序列长度；

class Solution {
public:int maxUncrossedLines(vector& nums1, vector& nums2) {int n1=nums1.size(),n2=nums2.size();vector> f(n1+1,vector(n2+1,0));for(int i=1;i<=n1;i++){for(int j=1;j<=n2;j++){f[i][j]=max(f[i-1][j],f[i][j-1]);if(nums1[i-1]==nums2[j-1]) f[i][j]=max(f[i][j],f[i-1][j-1]+1);}}return f[n1][n2];}
};

53.最大子数组和

之前贪心做过一次，贪心是每次都执行一个策略，只要和为负数就新开，不为负数就跟着；

而本次用动态规划，是在过程中每次都从几个状态里择优；

  • f(i)表示以i结尾的连续数组和最大值；
  • f(i)可以从f(i-1)转移过来，接着前面的连续数组，也可以新开一个连续序列；如果前面的加上自己还不如自己，那肯定新开(跟贪心是有相似之处的，这里的状态转移就是，如果前面的和为负数，自己就新开，如果前面的和不为负数，自己就跟着，每种状态进去的条件是固定的，所以也可以贪心)；
  • 初始f(0)是0，f其他的也初始为0，后一个从前一个转，初始为啥都问题不大；
class Solution {
public:int maxSubArray(vector& nums) {int n=nums.size();vector f(n+1,0);for(int i=1;i<=n;i++){f[i]=max(nums[i-1],f[i-1]+nums[i-1]);}int ans=-1e5;for(int i=1;i<=n;i++) ans=max(ans,f[i]);}
};
词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：案例23-服务出现频繁掉线情况

下一篇：Android kotlin 系列讲解（数据篇）SharedPreferences存储及测试

相关内容

热门资讯

【二层交换机】静态VLAN的配... 文章目录1.VLAN概述1.1 VLAN简介1.2 IEEE802.1Q帧格式1.3 VLAN优势1...
杭州湾跨海大桥造价多少亿（杭州... 本篇文章极速百科给大家谈谈杭州湾跨海大桥造价多少亿，以及杭州湾跨海大桥造价多少亿米对应的知识点，希望...
尽精微致广大的含义（尽精尽微尽... 本篇文章极速百科给大家谈谈尽精微致广大的含义，以及尽精尽微尽心尽全力对应的知识点，希望对各位有所帮助...
马6家族(马自达6、睿翼、阿特... 今天给各位分享马6家族(马自达6、睿翼、阿特兹)车型年款配置详解...的知识，其中也会对马自达6阿特...
既想无损安装又想声音效果好,森... 今天给各位分享既想无损安装又想声音效果好,森雅R9的这套音响改的恰...的知识，其中也会对森雅r9功...
SpringBoot集成 Sp... 文章目录一、CSRF跨站请求伪造攻击二、项目准备三、认识 SpringSecurity3.1 认证&...
Leedcode 392. 判... 题目 给定字符串 s 和 t ，判断 s 是否为 t 的子序列。 字符串的一个子序列是...
600w电机额定最大功率（电机... 今天给各位分享600w电机额定最大功率的知识，其中也会对电机功率600w是多少千瓦进行解释，如果能碰...
一桶原油等于多少升（一桶原油等... 本篇文章极速百科给大家谈谈一桶原油等于多少升，以及一桶原油等于多少升千克对应的知识点，希望对各位有所...
gmp是什么的简称（GMP是什... 本篇文章极速百科给大家谈谈gmp是什么的简称，以及GMP是什么的简称对应的知识点，希望对各位有所帮助...
什么是算法算法的特性有哪些（什... 本篇文章极速百科给大家谈谈什么是算法算法的特性有哪些，以及什么是算法算法的特性有哪些呢对应的知识点，...
剑指 Offer 47. 礼物... 题目： 链接：剑指 Offer 47. 礼物的最大价值 难度࿱...
【Linux】进程的基础概念 ... 进程一、进程的基本知识1、基本概念2、进程的描述 —— PCB3、task_ struct内容分类二...
[计算机图形学]反走样(前瞻预... 一、前言:走样的产生上一篇我们谈到了光栅化，在讲述光栅化时我们得到了光栅化之后的这样一...
Wine运行器3.2.0——优... 不写太多啥了，详细介绍看这里就行：https://bbs.deepin....
力帆320力帆320最新报价-... 本篇文章极速百科给大家谈谈力帆320力帆320最新报价-图片-参数，以及力帆320新车价格及图片对应...
惠州市车辆违章查询办法及车管所... 本篇文章极速百科给大家谈谈惠州市车辆违章查询办法及车管所地址，以及惠州市车辆违章查询官方网站对应的知...
运动地板和航空铝地板都耐磨,哪... 今天给各位分享运动地板和航空铝地板都耐磨,哪个更适应商务车做改装...的知识，其中也会对航空铝地板怎...
北戴河在哪里（北戴河在哪里看日... 今天给各位分享北戴河在哪里的知识，其中也会对北戴河在哪里看日出比较好进行解释，如果能碰巧解决你现在面...
flink部署-1.15 1. 版本说明 本文档内容基于 flink-1.15.x，其他版本的整理，...
【数据结构】二叉排序树大题（二... 记录一下数据结构大题啊，在大题里面经常会有一个二叉排序树。题目中会给出一组结点...
Python每日一练(2023... 目录 1. 有效的括号  ★ 2. 简化路径  ★★ 3. 整数转换英文表示  ★★★ dz...
ip是什么意思?（Tip是什么... 本篇文章极速百科给大家谈谈ip是什么意思?，以及Tip是什么意思英语对应的知识点，希望对各位有所帮助...
Spring01-入门、IOC... 文章目录学习目标一、Spring简介1 Spring课程介绍问题导入1.1 为什么要学1.2 学什么...
99977是什么意思汉语（99... 本篇文章极速百科给大家谈谈99977是什么意思汉语，以及99977是什么意思呀对应的知识点，希望对各...
摩西摩西是什么意思（日本摩西摩... 今天给各位分享摩西摩西是什么意思的知识，其中也会对日本摩西摩西是什么意思进行解释，如果能碰巧解决你现...
独立基础是什么（独立基础是什么... 本篇文章极速百科给大家谈谈独立基础是什么，以及独立基础是什么开挖对应的知识点，希望对各位有所帮助，不...
（待补充）小蒟蒻的刷题成长之路... 小蒟蒻的刷题成长之路 蓝桥杯的比赛流程和必考点_蓝桥杯省赛考点_时雨h的博客-CSDN博客 大一学生...
个人小站折腾后记 个人小站折腾后记 🏠个人主页：shark-Gao 🧑个...
福克斯首保多少公里保养一次（福... 本篇文章极速百科给大家谈谈福克斯首保多少公里保养一次，以及福克斯首保多少公里保养一次啊对应的知识点，...