《算法竞赛从入门到国奖》算法基础:动态规划-最长子序列

Yupureki:个人主页✨个人专栏:《C》 《算法》《Linux系统编程》《高并发内存池》《MySQL数据库》《个人在线OJ平台》Yupureki的简介:目录1. 最长上升子序列算法原理代码示例2. 合唱队形算法原理代码示例3. 最长公共子序列算法原理代码示例4. 编辑距离算法原理代码示例1. 最长上升子序列题目链接:B3637 最长上升子序列 - 洛谷算法原理状态方程:dp[i]表示以下标为i元素为结尾的最长子序列。最终结果是整张表中的最大值状态转移:既然是i元素为结尾因此我们需要与前面的子序列做连接。自己跟自己玩长度为1跟前面的所有子序列做连接前提是第i个元素的大小必须大于子序列的末尾元素。初始化:不用单独初始化每次填表的时候先把这个位置的数改成1即可。填表顺序:从左到右代码示例#include iostream #include vector using namespace std; int main() { int n; cin n; vectorint v(n); vectorint dp(n); for (int i 0; i n; i) { int num; cin num; v[i] num; } int ret 0; for(int i 0;in;i) { dp[i] 1; for(int j i - 1;j0;j--) { if(v[i] v[j]) { dp[i] max(dp[i],dp[j] 1); ret max(ret,dp[i]); } } } cout ret; return 0; }2. 合唱队形题目链接:P1091 [NOIP 2004 提高组] 合唱队形 - 洛谷算法原理状态表示:两张dp[i]表。dp1[i]表示以第i个元素为结尾从左到右的最长子序列的长度dp2[i]表示以第i个元素为结尾从右到左的最长子序列的长度最终整个以中间元素为分割线从左到右从右到左都呈递增的序列长度即为len max(dp1[i] dp2[i])要分出去的学生个数即为n - len状态转移:分别从左向右从右向左打两张表即可初始化:不需要做额外的初始化填表顺序:分别从左向右从右向左代码示例#include iostream #include vector using namespace std; int main() { int n;cinn; vectorint v; vectorint dp1(n,1); vectorint dp2(n,1); for(int i 0;in;i) { int num;cinnum; v.push_back(num); } for(int i 0;in;i) { for(int j 0;ji;j) { if(v[j] v[i]) dp1[i] max(dp1[i],dp1[j]1); } } for(int i n-1;i0;i--) { for(int j n-1;ji;j--) { if(v[j] v[i]) dp2[i] max(dp2[i],dp2[j]1); } } int ret 0; for(int i 0;in;i) { ret max(ret,dp1[i] dp2[i] - 1); } coutn-ret; return 0; }3. 最长公共子序列题目链接:牛可乐和最长公共子序列算法原理状态表示:dp[i][j]表示第一个子序列前i个元素中第二个子序列前j个元素中最长的公共子序列长度状态转移:如果s1[i] s2[j]说明可以以这个字母做结尾形成公共子序列。那么只需要找到第一个序列前i - 1,第二个序列前j - 1中找到最长的公共子序列拼接上去即可。即dp[i][j] dp[i - 1][j - 1] 1;如果s1[i] ! s2[i]说明最长公共子序列不可能同时以s1[i]和s2[j]做结尾那么有两种策略在s1的前i - 1,s2的前j个中找在s1的前i ,s2的的前j - 1个中找最终结果取二者最大值dp[i][j] max(dp[i - 1][j], dp[i][j - 1]);初始化:不需要做额外的初始化填表顺序:从左到右代码示例#include iostream #include vector using namespace std; int main() { string a, b; while (cin a b) { vectorvectorint dp(a.size() 1, vectorint(b.size() 1)); for (int i 1; i a.size(); i) { for (int j 1; j b.size(); j) { if (a[i - 1] b[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[a.size()][b.size()] endl; } }4. 编辑距离题目链接:P2758 编辑距离 - 洛谷算法原理状态表示:dp[i][j]表示考虑a的前i个元素b的前j个元素将a转换成b的最少操作次数状态转移:当a[i] b[j]时直接考虑dp[i-1][j-1]即可当a[i] ! b[j]时删除a[i]:相当于dp[i-1][j]插入一个字符(b[j]):相当于dp[i][j - 1]将a[i]改为b[j]:相当于dp[i-1][j-1]取这三者的最小值加1即可初始化:不需要做额外的初始化填表顺序:从左到右代码示例#include iostream #include string #include vector using namespace std; int main() { string a,b;cinab; int n a.size(); int m b.size(); vectorvectorint dp(n1,vectorint(m1)); for (int i 0; i n; i) { dp[i][0] i; } for (int j 0; j m; j) { dp[0][j] j; } for(int i 1;in;i) { for(int j 1;jm;j) { if(a[i-1] b[j-1]) dp[i][j] dp[i-1][j-1]; else dp[i][j] min(dp[i][j-1],min(dp[i-1][j],dp[i-1][j-1])) 1; } } coutdp[n][m]; return 0; }