DP(动态规划)【3】 最长公共子序列 最长回文子串

目录

1.最长公共子序列

状态转移方程需要二维数组，1-dim已经不太够了

又是这个问题：如何读入字符串

2.最长回文子串

---

1.最长公共子序列

状态转移方程需要二维数组，1-dim已经不太够了

这里dp[i][j]是说S的前i位与T的前j位公共序列，所以前i位是下标至i-1位置（≤，闭）

所以，最后是到dp[lenA][lenB].

同时，判断时，要s[i-1]==t[j-1]。注意向左偏移一位

又是这个问题：如何读入字符串

答案用的是cin>>#string

再次参照之前的

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
using namespace std;
const int N=102,maxn=10;int n,m,k,dp[N][N]={0};
char str1[N],str2[N];
int main()
{scanf("%s",str1);scanf("%s",str2);int l1=strlen(str1);int l2=strlen(str2);int ans=0;for(int i=0;i<=l1;i++) dp[i][0]=0;
for(int i=0;i<=l2;i++) dp[0][i]=0;for(int i=1;i<=l1;i++)
{for(int j=1;j<=l2;j++)
{
if(str1[i-1]!=str2[j-1]) //注意这里要偏移一位 
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
else dp[i][j]=dp[i-1][j-1]+1;
}
}
printf("%d",dp[l1][l2]);}

所以可以scanf("%s",#cstring) 

读取字符串长度？

试一波

2.最长回文子串

状态：仍然是二维数组，dp[i][j]是从i位到j位是否是回文串

如何遍历？

不像上题，直接fori=0……forj=0

应该是第一憧循环表示子串长度，依次遍历长度为3,4，……的所有子串（实现写好长度为1&2的边界条件），然后更新ans

转移方程

if str【j】=str【j+i-1】

&& dp【i+1】【i+j-2】

则dp【i】【j】=1；

代码

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
using namespace std;
const int N=102,maxn=10;int n,m,k,dp[N][N]={0};
char str[N],str2[N];
int main()
{scanf("%s",str);int l1=strlen(str);int ans=1;for(int i=0;i<l1;i++) dp[i][i]=1;
//for(int i=0;i<l1;i++)
//{for(int j=0;j<l1;j++)
//{printf("-%d-",dp[i][j]);
//
//
//}
//printf("\n");
//}
//for(int i=0;i<l1-1;i++)
{dp[i][i+1]=int(str[i]==str[i+1]);dp[i+1][i]=int(str[i+1]==str[i]);if(str[i]==str[i+1]) ans=2;//printf("*%d*",dp[i][i+1]);
}for(int i=3;i<=l1;i++)//枚举长度 
{for(int j=0;j+i-1<=l1-1;j++)//枚举长度为i的子串 
{
if(str[j]==str[j+i-1])
{if(dp[j+1][j+i-1-1]) 
{dp[j][j+i-1]=1;
ans=i;//printf("?"); }
}
//lozjujzve}
}
//
//for(int i=0;i<l1;i++) dp[i][i]=1;
//for(int i=0;i<l1;i++)
//{for(int j=0;j<l1;j++)
//{printf("-%d-",dp[i][j]);
//
//
//}
//printf("\n");
//}printf("%d",ans);}

强调一下，不能对s和s[::-1]求最长公共子序列，我一直以为是可以的

理由如下：