题目描述

blablabla

样例

blablabla

算法1

$O(n^2)$

其中状态计算需要分为四种情况，无i无j (f[i - 1, j - 1]), 无i有j (f[i - 1, j]), 有i无j (f[i,j -1]) 以及有i有j (f[i - 1, j - 1] + 1);
此处需要强调的两点：
1.无i有j 与 f[i - 1, j]并不是完全等价，因为f[i - 1, j]表示i - 1，j结尾的公共子序列数量，但不一定有a[i - 1] = b[j]，只是包含这种情况。由此可见，f[i - 1, j]与f[i, j - 1]会出现重合，但因为求的是最大值，所以不影响。
2.无i无j的情况被后者所包含，所以可以省略。由此则需比较，f[i - 1, j]，f[i, j - 1]以及(f[i - 1, j - 1] + 1) (当a[i] = b[j] 是才需要讨论有i有j)

Java 代码

import java.util.*;
import java.io.*;

public class Main{
    private static int N, M;
    private static int[][] f;
    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args) throws IOException{
        String[] s1 = read.readLine().split("\\s+");
        N = Integer.parseInt(s1[0]);
        M = Integer.parseInt(s1[1]);
        f = new int[N+1][M+1];  

        String a = read.readLine();
        String b = read.readLine();

        for(int i = 1; i <= N; i++){
            for(int j = 1; j <= M; j++){
                f[i][j] = Math.max(f[i-1][j], f[i][j-1]);
                if(a.charAt(i-1) == b.charAt(j-1)){
                    f[i][j] = Math.max(f[i][j], f[i-1][j-1]+1);
                }
            }
        }

        System.out.println(f[N][M]);
    }

}