DP之字符串算法

之前写的关于DP问题的一般分析思路：DP之01背包详解
这篇的话主要是来学习常见的序列问题中用到的DP。

第一种、最长上升子序列

1.1 题目信息：

1.2 分析：

1.2.1 状态表示：

f[i]记录所有以第i个数结尾的上升子序列

1.2.2 确定状态转移方程

如何更新f[i]的值呢？
其实在这个类型的题目中是枚举以i为结尾的序列的上一个数是哪一个。于是我们需要变量j从1枚举到i-1,如果a[i]>a[j]并且f[i]>f[j]+1,那么我们认为这是可以用来更新f[i]的值。
所以可以得出状态转移方程为:

if（a[i]>a[j])//可以保证是上升序列
	f[i]=max(f[i],f[j]+1);//通过不断的更新最终保证是最长上升序列

1.2.3 边界：

f[1]=1;

1.3 代码：

# 时间：2022.09.27  21点47分
#include
#include
#include
using namespace std;
const int N=100;
int a[N];
int f[N];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    
    for(int i=1;i<=n;i++){
        f[i]=1;//单个数字也可以认为是长度为1的序列
        for(int j=1;j<i;j++)
            if(a[i]>a[j])//保证得到得到上升序列
                f[i]=max(f[i],f[j]+1);//更新得到的保证是最长上升序列
    }
    int mmax=-1;
    for(int i=1;i<=n;i++)   mmax=max(f[i],mmax);
    cout<<mmax<<endl;
    return 0;
}

1.4 最长不下降子序列：

和最长上升序列的区别就是元素可以相同。
只需要将核心代码 f[i] > f[j] 改为 f[i] >= f[j]即可

第二种：最长公共子序列（LCS）

2.1 题目信息：

2.2 分析：

2.2.1 状态表示：

==f[i,j]:==所有在第 1个序列的前 i 个字母中出现，且在第二个序列的前 j 个字母中出现的子序列的集合的最大值。

2.2.2 状态转移方程：

这种情况下需要看a[i]和b[i]是否在公共序列中：

1. 若a[i]=b[j],则a[i]与b[j]在公共子序列中，f[i][j]=f[i-1][j-1]+1
2. 若a[i]!=b[j],且a[i]不在公共子序列中,则可去掉a[i],所以f[i][j]=f[i-1][j]
3. 若a[i]!=b[j],且b[j]不在公共子序列中，则可去掉b[j]，所以f[i][j]=f[i][j-1]
4. 若a[i]!=b[j],且a[i]和b[j]都不在公共子序列中，则可去掉a[i]和b[j]，所以f[i][j]=f[i-1][j-1] ,但是其实可以发现这种情况是包含在2和3中的，所以不用单独写出。

转移方程：

1. 如果a[i]!=b[j] 那么 f[i][j]=max(f [i-1] [j],f [i] [j-1] )
2. 如果a[i]=b[j] 那么 f[i][j]=f [i-1] [j-1]+1

2.2.3 边界：

f[0][j]=0,f[i][0]=0;

2.3 代码：

// 时间：2022.07.13 17点48分
#include
#include
using namespace std;

const int N=1010;
int n,m;
char a[N],b[N];
int f[N][N];
int main()
{
   cin>>n>>m;
   scanf("%s%s",a+1,b+1);
   
   for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
        f[i][j]=max(f[i-1][j],f[i][j-1]);
        if(a[i]==b[j]) f[i][j]=max(f[i][j],f[i-1][j-1]+1);
    }    
    cout<<f[n][m]<<endl;
    return 0;
}

第三种、最长公共子串(LCS)

和最长公共子序列的区别：

公共子串：字符必须是连续相等的
公共子序列：字符必须是相等的，可以不连续

3.1 题目信息：

3.2 分析：

3.2.1 状态表示：

只有当两字符串中的字符连续相等时，公共子串的长度才不断增加，否则清零
状态表示:
f[i][j]表示以a[i]和b[j]为结尾的公共子串的长度

3.2.2 状态转移方程：

我们可以先模拟一下样例：当i=1时

当i=2时：

转移方程：
我们可以从中找出规律来：只有当a[i]和b[j]相等时才能构成字串，其余的情况都是都不行。

1. 若a[i]=b[j]，则可以构成公共子串,f[i] [j] = f [i-1 ][j-1] +1
2. 若a[i]!=b[j],则不能构成公共子串，f[i][j] =0

3.2.3 边界：

f[0][j]=0
f[i][0]=0

3.3 代码：

// 时间：2022.09.28 21点07分
#include
using namespace std;
int f[100][100];
int main ()
{
    string a,b;
    cin>>a>>b;
    int mmax=-1;
    for(int i=1;i<=a.size();i++){
        for(int j=1;j<=b.size();j++){
            if(a[i-1]==b[j-1])//注意此时下标
                f[i][j]=f[i-1][j-1]+1;
            else f[i][j]=0;
            if(f[i][j]>mmax) mmax=f[i][j];
            //在更新f数组的同时就可以将最大值找到
        }
    }
    cout<<mmax<<endl;
    return 0;
}