DP经典例题——LIS&LCS

LCS

最长公共子序列，英文缩写为LCS(Longest Common Subsequence)。其定义是，一个序列 S ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则 S 称为已知序列的最长公共子序列。而最长公共子串(要求连续)和最长公共子序列是不同的.

《算法竞赛进阶指南》上没有给出标程怎么会要标程呢所以给出程序或许并非最佳

状态表示：f[i]表示以a[i]为结尾的“最长上升子序列”的长度
阶段划分：子序列的结尾位置
转移方程：

\[f[i]=max(f[j]+1),0<=j<i,a[j]<a[i]
\]
边界：f[0]=0

模板代码：

//最长公共子序列

#include<bits/stdc++.h>

using namespace std;

char a[100000],b[100000];

int dp[10000][10000],n;	//dp为转移数组

int main(){

	scanf("%d",&n);

	for(int i=1;i<=n;i++)	cin>>a[i];

	for(int i=1;i<=n;i++)	cin>>b[i];

	dp[n][0]=0,dp[0][n]=0;	//初始化

	for(int i=1;i<=n;i++){

		for(int j=1;j<=n;j++){

			dp[i][j]=max(dp[i-1][j],dp[i][j-1]);	//状态转移方程

			if(a[i]==b[j])	dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);

		}

	}

	printf("%d",dp[n][n]);

	return 0;

}

例题：P1439 【模板】最长公共子序列

LIS

最长上升子序列（Longest Increasing Subsequence），简称LIS，也有些情况求的是最长非降序子序列，二者区别就是序列中是否可以有相等的数。

《算法竞赛进阶指南》上依旧没有给出标程怎么会要标程呢所以给出程序或许并非最佳

状态表示：f[i,j]表示前缀子串a[1-i]与b[1-j]的“最长公共子序列”的长度
状态划分：已处理的前缀长度
转移方程：

\[f[i,j]=max(max(f[i-1,j],f[i,j-1]),f[i-1,j-1])\\
if(a[i]==b[i])
\]
边界：f[i,0]=f[0,j]=0

模板代码：

//最长上升子序列

#include<bits/stdc++.h>

using namespace std;

int a[100000],n,dp[100000],ans;

int main(){

	scanf("%d",&n);

	for(int i=1;i<=n;i++)	scanf("%d",&a[i]);

	dp[0]=0;	//初始化

	for(int i=1;i<=n;i++){

		for(int j=0;j<i;j++){

			if(a[j]<a[i])	dp[i]=max(dp[i],dp[j]+1);	//状态转移

		}

	}

	for(int i=1;i<=n;i++)	ans=max(ans,dp[i]);

	printf("%d",ans);

	return 0;

}

巴特西

DP经典例题——LIS&LCS

DP经典例题——LIS&LCS

LCS

LIS

最新文章

热门文章