动态规划 线性 DP 五大经典模型：LIS、LCS、合唱队形、编辑距离 详解与模板

Ne0inhk

— 16 min read
动态规划 线性 DP 五大经典模型：LIS、LCS、合唱队形、编辑距离 详解与模板

文章目录

经典线性 dp 问题有两个：最⻓上升⼦序列（简称：LIS）以及最⻓公共⼦序列（简称：LCS），这两道题⽬的很多⽅⾯都是可以作为经验，运⽤到别的题⽬中。⽐如：解题思路，定义状态表⽰的⽅式，推到状态转移⽅程的技巧等等。
因此，这两道经典问题是需要我们重点掌握的。

最长上升子序列

题目描述

在这里插入图片描述

题目解析
本题介绍最长上升子序列的一般解法，当数据量不大时用这种解法。
在此之前，小编先区分一下子数组和子序列，子数组需要是连续的，而子序列可以是间断的。

1、状态表示
dp[i]表示以i结尾的所有子序列中，最长的上升子序列。
2、状态转移方程
还是以最后一步推导状态转移方程，分两种情况：
一、当序列长度为1时，因为dp[i]自己本身就是一个子序列，所以dp[i]的最小取值可能是1（比如总序列是一个递减序列的话，那么每个dp[i]的取值都会是1）
二、当序列长度大于1时，如果第i个格子前面的所有格子中有比第i个格子小的格子，记为j，那么第i个格子就可以挂在j格子后面组成一个序列，序列长度就是dp[j]加1，因为我们要求最长上升子序列，所以需要遍历dp数组中从1到i-1的所有值，找出所有a[j]小于a[i]的格子，从中选出dp[j] + 1的最大值，该值为dp[i]的取值。

在这里插入图片描述


所以状态转移方程如下图所示：

在这里插入图片描述


3、初始化
因为我们没遍历到一个格子都会先把dp[i]置为1，所以dp数组不用初始化，用默认值0即可。
4、填表顺序
从左往右
5、输出结果
结果为dp数组从1到n的所有取值的最大值。

代码

#include<iostream>#include<algorithm>usingnamespace std;constint N =5010;int n;int a[N], dp[N];intmain(){//处理输入 cin >> n;for(int i =1; i <= n; i++){ cin >> a[i];}//初始化//按序填表int ret =0;for(int i =1; i <= n; i++){ dp[i]=1;for(int j =1; j < i; j++){//选出dp数组中1到i-1所有格子的最大值，把最大值加一赋给dp[i]if(a[j]< a[i]){ dp[i]=max(dp[i], dp[j]+1);}} ret =max(ret, dp[i]);} cout << ret << endl;return0;}

【模板】最长上升子序列

题目描述

在这里插入图片描述

题目解析
本题介绍最长上升子序列的推广解法，当数据量较大时用这种解法。
这里会利用贪心加二分优化时间复杂度，但是需要注意，这种方式是有局限性的，它只能求出最长上升子序列的长度，而不能还原出整个最长上升子序列。

在研究最长上升子序列时，其实只用关心序列的长度和序列最后一个元素是谁，我们并不关心序列具体长什么样子，本题是求解思路就是基于此实现的。
1、状态表示
对于原序列来说，我们先找出所有长度刚好是 i 的上升子序列（比如 i=3 时，就是所有长度为 3 的上升子序列），然后把这些子序列的最后一个数都列出来，在这些数里找最小的那个，这个最小的数就是 dp [i]。
这里用最小值充当dp[i]是用到了贪心的思想：要让序列尽可能长，就要让序列末尾元素尽可能小，让序列后面能挂更多元素。
2、状态转移方程
除了dp数组，我们还需要用一个全局变量len来存储最长上升子序列的长度。
填dp数组时我们要遍历整个a数组，首先处理边界情况，当len为0（序列为空）或者a[i]比dp[len]大（a[i]比最长序列的末尾元素还大）时，直接把len++，然后把a[i]赋值给dp[len]。否则就是一般情况，也就是序列本身已经有元素了，并且a[i]的值小于最长序列的末尾元素，这时我们要更新dp数组，但是len保持不变，更新策略是在dp数组中二分查找所有大于等于a[i]的元素中，其中的最小值所在的位置，然后把a[i]的值赋给该位置。（本质就是维护dp数组的特性：dp [i]为长度为i的所有子序列末尾元素的最小值）
3、初始化
无
4、填表顺序
从左往右
5、输出结果
len
代码

#include<iostream>usingnamespace std;constint N =1e5+10;int n;int a[N], dp[N];int len;//记录最长上升子序列长度intmain(){//处理输入 cin >> n;for(int i =1; i <= n; i++){ cin >> a[i];}//遍历原数组并填dp数组for(int i =1; i <= n; i++){if(len ==0|| a[i]> dp[len]){//边界情况，len和a[i]大于最长合法序列的末尾元素时//直接把a[i]放在dp数组++len处 dp[++len]= a[i];}//在dp数组中二分查找大于等于a[i]的最小值int l =1, r = len;while(l < r){int mid =(l + r)/2;if(dp[mid]>= a[i]){//答案在左半部分，包含mid r = mid;}else l = mid +1;}//把a[i]赋值给查找到的dp数组中大于等于a[i]的最小值 dp[l]= a[i];} cout << len;return0;}

合唱队形

题目描述

在这里插入图片描述

题目解析
本题是最长上升子序列问题的一个模板题，比较简单小编就简单说明一下。
依据题意，要找一个最长的先递增在递减的子序列，要让该子序列最长，就要分别让递增序列和递减序列都尽可能长，最终答案就是遍历所有同学找到一个同学i，以他为顶峰的递增序列+递减序列长度是最大的，但是需要注意同学i既在递增序列中也在递减序列中，相当于递增序列+递减序列把同学i算了两遍，所以最终答案要减一。
所以我们要对每一个同学求他的最长的递增子序列和最长递减的子序列，求最长递减的子序列也就相当于求从右往左的最长递增子序列，根据求最长的递增子序列的通用方法，我们知道dp[i]就表示以i结尾的所有子序列中，最长的上升子序列。本题我们要开两个dp数组，分别维护从左往右的最长递增子序列和从右往左的最长递增子序列。

代码

#include<iostream>#include<algorithm>usingnamespace std;constint N =110;//dp1维护从左往右的最长上升子序列//dp2维护从左往右的最长上升子序列int a[N], dp1[N], dp2[N];int n;intmain(){ cin >> n;for(int i =1; i <= n; i++){ cin >> a[i];}//初始化//按序填表//1.填dp1数组for(int i =1; i <= n; i++){ dp1[i]=1;for(int j =1; j < i; j++){if(a[j]< a[i]) dp1[i]=max(dp1[i], dp1[j]+1);}}//2.填dp2数组for(int i = n; i >=1; i--){ dp2[i]=1;for(int j = n; j > i; j--){if(a[j]< a[i]) dp2[i]=max(dp2[i], dp2[j]+1);}}//输出结果int ret =0;for(int i =1; i <= n; i++){//因为中间i的同学算了两遍，所以需要减一 ret =max(ret, dp1[i]+ dp2[i]-1);} cout << n - ret;return0;}

牛可乐和最长公共子序列

题目描述

在这里插入图片描述

题目解析
痛点：存储字符串问题！用string存储下标从0开始！
解决方案：
1、修改下标映射：i -> i - 1 j->j - 1
2、s = " " + s; + s;

本题小编不仅会讲题解，还会介绍一下如何分析两个数组的dp问题。
1、初始化
用一个二维数组dp[i][j]，表示s字符串1到i区间内和t字符串1到j区间内，所有子序列中，最长公共子序列的长度。
2、状态转移方程
状态转移方程要分两种情况讨论：
1、当遍历到两个字符串相同的元素时（s[i] == t[j]），表示这个相同的元素的最长公共子序列的元素之一，要把这个这一对相同的元素选上，也就是把当前公共子序列长度在之前的基础上加1，那要如何找到之前的公共子序列长度呢？其实之前的公共子序列长度就是s字符串1到i - 1区间内和t字符串1到j区间内的最长公共子序列的长度，也就是dp[i - 1][j - 1]，所以这种情况的状态转移方程：
dp[i][j] = dp[i - 1][j - 1] + 1
2、当遍历到两个字符串不同的元素时（s[i] != t[j]），一定不会把这一对不同的元素选到，这时为了填dp[i][j]就需要退而求其次，求在不看s[i]的情况下的最长公共子序列、在不看t[j]的情况下的最长公共子序列和求在不看s[i]并且不看t[j]的情况下的最长公共子序列，也就是分三种情况讨论：
在s数组的1到i区间和t数组的1到j - 1区间找最长公共子序列
在s数组的1到i - 1区间和t数组的1到j区间找最长公共子序列
在s数组的1到i - 1区间和t数组的1到j-1区间找最长公共子序列
dp[i][j]就是在这三种情况中取最值，但对于这种三种情况中取最值的逻辑，因为情况3是包含在情况1、2中的，所以情况3的方案一定小于等于情况1、2，所以在前两种情况中取最值即可。
dp[i][j] = max（dp[i][j - 1]，dp[i - 1][j]）

在这里插入图片描述


3、初始化
全部为0即可，因为本题的长度必定大于0，0不会干扰max取最大值的逻辑。
本题虽然是多组测试用例，但是填表是覆盖并且有顺序的，所以每组用例不用重置。
4、填表顺序
根据状态转移方程，填[i][j]时会用到左、上、和左上三个位置的格子，所以填表顺序是从上往下、从左往右。

在这里插入图片描述


5、输出结果
假设s字符串长度为n，t字符串长度为m:
dp[n][m]

代码

#include<iostream>#include<string>#include<algorithm>usingnamespace std;constint N =5010;int dp[N][N]; string s, t;intmain(){while(cin >> s >> t){int n = s.size();int m = t.size();//初始化//按序填表for(int i =1; i <= n; i++){for(int j =1; j <= m; j++){if(s[i -1]== t[j -1]){ dp[i][j]= dp[i -1][j -1]+1;}else{ dp[i][j]=max(dp[i -1][j], dp[i][j -1]);}}}//输出结果 cout << dp[n][m]<< endl;}return0;}

编辑距离

题目描述

在这里插入图片描述

题目解析
1、状态表示
本题思路继续延续上一题的双数组dp问题，状态表示也类似：dp[i][j]表示把s字符串的1到i子字符串变成t字符串的1到j子字符串的最少操作次数。
2、状态转移方程
还是和上一题类似分两种情况讨论：
1、当遍历到两个字符串相同的元素时（s[i] == t[j]），说明此时不需要修改s数组最后一个元素，也就是对于dp[i][j]来说不需要将操作数加一，仅需要拿到把s字符串的1到i - 1子字符串变成t字符串的1到j - 1子字符串的最少操作次数即可，拿到的该最少操作次数为dp[i][j]的取值。
2、当遍历到两个字符串不同的元素时（s[i] != t[j]），说明此时需要修改s数组最后一个元素，因为题目给出了三种修改方式，所以这里我们要分三种情况讨论：
1.删除s字符串最后一个元素，然后把s字符串的1到i - 1子字符串变为t字符串，把s字符串的1到i - 1子字符串变为t字符串的最少操作次数在dp[i - 1][j]中，因为有删除操作，所以还需要加1。dp[i][j] = dp[i - 1][j] + 1

在这里插入图片描述

2、在s字符串最后面插入t字符串的最后一个元素，然后把s字符串的1到i字符串变为t字符串的1到j - 1子t子字符串。dp[i][j] = dp[i][j - 1] + 1

在这里插入图片描述

3、把s字符串最后一个元素改为t字符串最后一个元素，然后把s字符串的1到i - 1子字符串变为t字符串的1到j - 1子字符串。dp[i][j] = dp[i - 1][j - 1] + 1

在这里插入图片描述

3、初始化
本题初始化需要结合题目的实际意义，虽然题目数据范围的字符串长度从1开始，但是对于本题来说，研究字符串为空时还是有必要的，当把一个空串转换为一个长度为1的字符串时最少字符操作次数是1（插入1次），同理把一个空串转换为一个长度为2的字符串时最少字符操作次数是2，所以对于dp数组的边界情况dp[0][1]要初始化为1，dp[0][2]要初始化为2，依次类推。
当把长度为1的字符串转换为一个空串时最少字符操作次数是1（删除一次），同理当把长度为2的字符串转换为一个空串时最少字符操作次数是2，所以对于dp数组的边界情况dp[1][0]要初始化为1，dp[2][0]要初始化为2，依次类推。

在这里插入图片描述

4、填表顺序
从上往下，从左往后
5、输出结果
dp[n][m]

代码

#include<iostream>#include<string>#include<algorithm>usingnamespace std;constint N =2010;int dp[N][N]; string s, t;intmain(){ cin >> s >> t;int n = s.size();int m = t.size();//初始化for(int i =1; i <= n; i++){ dp[i][0]= i;}for(int i =1; i <= m; i++){ dp[0][i]= i;}//按序填表for(int i =1; i <= n; i++){for(int j =1; j <= m; j++){if(s[i -1]== t[j -1]){ dp[i][j]= dp[i -1][j -1];}else{//删int a = dp[i -1][j]+1;//插int b = dp[i][j -1]+1;//改int c = dp[i -1][j -1]+1; dp[i][j]=min({ a, b, c });}}}//输出结果 cout << dp[n][m]<< endl;return0;}

以上就是小编分享的全部内容了，如果觉得不错还请留下免费的赞和收藏
如果有建议欢迎通过评论区或私信留言，感谢您的大力支持。
一键三连好运连连哦~~

在这里插入图片描述

Read more

程序员怎样才能学好算法?这本书送几本给大家!

程序员怎样才能学好算法?这本书送几本给大家!

文章目录 * 前言 * 一、笔者对算法的理解 * 二、写书的初衷及过程 * 三、主要内容 * 四、本书的内容 * 五、联合推荐 * 六、购买方式 * 七、《算法秘籍》 * 中奖者名单 前言 提示：这里可以添加本文要记录的大概内容： 数据结构和算法是计算机科学的基石，是计算机的灵魂，要想成为计算机专业人员，学习和掌握算法是十分必要的。不懂数据结构和算法的人不可能写出效率更高的代码。计算机科学的很多新行业都离不开数据结构和算法作为基石，比如大数据、人工智能等。底层开发中也需要使用非常多的数据结构和算法知识，以保证底层系统的稳定性和高效性。 提示：以下是本篇文章正文内容，下面案例可供参考 一、笔者对算法的理解 计算机科学家尼古拉斯·沃斯在计算机领域有一句人尽皆知的名言： “算法+数据结构=程序”（Algorithms+Data Structures=Programs） 所以数据结构和算法是程序员必须掌握的技能。尤其是到一些大公司面试的时候，算法更是一个少不了的环节，熟练掌握数据结构和算法，可以开拓我们的视野，提高我们的逻辑思维能力，

By Ne0inhk
优选算法——滑动窗口2

优选算法——滑动窗口2

优选算法——滑动窗口 1.1004. 最大连续1的个数 III 题目描述 思路分析 这道题的核心是：找一个最长的子数组，其中最多包含 k 个 0。 经典的 滑动窗口 问题。 为什么用滑动窗口？ * 我们需要连续区间 → 滑动窗口天然适合 * 窗口内维护「0 的个数 ≤ k」这个约束 * 窗口扩张：右指针右移，遇到 0 就计数 * 窗口收缩：当 0 的个数超过 k，左指针右移直到满足条件 算法流程 1. 初始化：left = 0, zeroCount = 0, maxLen = 0 2. 遍历数组，right 指针右移： -

By Ne0inhk
【DeepSeek】一文详解GRPO算法——为什么能减少大模型训练资源？

【DeepSeek】一文详解GRPO算法——为什么能减少大模型训练资源？

GRPO，一种新的强化学习方法，是DeepSeek R1使用到的训练方法。 今天的这篇博客文章，笔者会从零开始，层层递进地为各位介绍一种在强化学习中极具实用价值的技术——GRPO（Group Relative Policy Optimization）。如果你是第一次听说这个概念，也不必慌张，笔者会带领你从最基础的强化学习背景知识讲起，一步步剖析其来龙去脉，然后再结合实例讲解 GRPO 在实际应用中的思路和操作示例，最后再和其他近似方法对比，看看它和当下主流的 PPO（近端策略优化）等方法究竟有何区别与联系。 强烈推荐看完此帖子后再阅读另一帖——适当练习，强化记忆：【DeepSeek】大模型强化学习训练GRPO算法，你学会了吗？ GRPO原论文链接：https://arxiv.org/abs/2402.03300 GRPO中译文链接：https://blog.ZEEKLOG.net/qq_38961840/article/details/145384346 为什么需要关注强化学习与策略优化？ 在正式开始介绍 GRPO

By Ne0inhk
数据结构-单链表

数据结构-单链表

单链表 * 概念与结构 * 结点 * 链表的性质 * 链表的打印 * 实现单链表 * 头文件 * 源文件 * 单链表的打印 * 单链表申请新节点内存 * 尾插 * 头插 * 尾删 * 头删 * 查找 * 在指定位置之前插入数据 * 在指定位置之后插入数据 * 删除pos结点 * 删除pos之后的结点 * 销毁链表 * 链表的分类 * 代码地址 概念与结构 概念：链表是⼀种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 逻辑结构：线性 物理结构（存储结构）：不一定是线性的 链表就类似一个火车，车头是哨兵位（可有可无），车厢是节点 * 将火车里的某节车厢去掉或加上，不会影响其他车厢，每节车厢都是独立存在的。 在链表⾥，每节“车厢”是什么样的呢？ \color{red}{在链表⾥，每节“车厢”是什么样的呢？

By Ne0inhk