2021-04-07 PAT A1045

LCS做法
一开始我也是想不到能这么做的啊，然后我去借鉴了一下别人的，就明白啦
改动的地方就在A[i] == B[i]这里，因为是有两个元素相等了，如果是按照原来LCS的做法，那么在这个矩阵里面填的每个数，都是一定比它的左边上面还有左上的元素大的，在这道题中，出现了重复的字符，那么这个数字的左边很有可能比从上层转移来的大，为什么？因为有了重复的数字！所以可以这么做。
其实吧，真正要解的话，还是要自己推出正确的状态转移方程才行。

#include<cstdio>
#include<algorithm>
using namespace std;
int A[210],B[10010],dp[210][10010];
int main(){
    int n;scanf("%d %d",&n,&n);
    for(int i = 1;i <= n;i++) scanf("%d",&A[i]);
    int n2;scanf("%d",&n2);
    for(int i = 1;i <= n2;i++) scanf("%d",&B[i]);
    for(int i = 1;i <= n;i++)dp[i][0] = 0;
    for(int i = 1;i <= n2;i++) dp[0][i] = 0;
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= n2;j++){
            if(B[j] == A[i])
                dp[i][j] = max(dp[i - 1][j - 1],dp[i][j - 1]) + 1;
            else
                dp[i][j] = max(dp[i - 1][j],dp[i][j - 1]);
        }
    }
    printf("%d",dp[n][n2]);
    
}