题目描述
(自用)
最长公共子序列dp,数据范围10^3,看题目想到要确定一个最大长度,必然要遍历所有情况,想到dp,f[n][m]表示a串前n项和b串前m项的最大子序列长度.dp元分析三步走,函数功能,初始化,递推关系。为什么会确定为这个函数功能而在最长上升子序列不将其表示为前n项最长子序列。公共子序列能找出明显的的控制关系,f[i]][j]可以清晰找出上一层推下一层。而最长上升子序列表示成前n项时,很难找出下层和上层的关系,(有可能是一维这种结构导致的)。所以我们还得找另外的性质,发现以a[i]为结尾的最长上升子序列可以匹配这种问题(隐含着双指针的思想).
算法1
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 1010
char arr[N],brr[N];
int f[N][N];
int n,m;
void dp()
{
for(int i= 1 ;i <= n;i++)
{
for(int j = 1; j <= m ;j++)
{
if(arr[i] == brr[j])
f[i][j] = f[i - 1][j - 1] + 1;
else
f[i][j] = max(f[i][j - 1],f[i - 1][j]);
}
}
cout << f[n][m];
}
int main()
{
cin >> n >> m;
for(int i= 1 ;i <=n;i++)
cin >> arr[i];
for(int i= 1 ;i <=m;i++)
cin >> brr[i];
dp();
}