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[1i]與b[1j]的“最長公共子序列”的長度
-
狀態劃分：已處理的前綴長度
-
轉移方程：
\[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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/538039.html
標籤：其他