DP算法一 （带逆推）

1. $f(i,j)$表示“只考虑数组$a$前$i$个和数组$b$的前$j$个的选法集合”，属性：公共子序列长度$Max$
2. 状态计算，对于$a_i$和$b_j$，有四种情况
   • 都不选：$f(i,j) = f(i-1, j-1)$
   • 都选：$f(i,j) = f(i-1, j-1) + 1$，当且仅当$a_i = b_j$时成立
   • 选$i$不选$j$：$f(i,j) = f(i, j-1)$，这里有重复的情况，$f(i,j-1)$有可能选$i$也有可能不选$i$，但是求的是最大值。不是方案总和，所以重复无影响，下同
   • 选$j$不选$i$：$f(i,j) = f(i-1, j)$
   • 综上：后两种情况都包含了“都不选”的情况，故第一种情况省略，$f(i,j) = max(f(i-1,j),f(i,j-1),f(i-1,j-1)+1)$
3. 逆推具体方案
   1. 从$a$、$b$末尾开始向前推导
   2. 如果$f(i,j)=f(i-1,j-1)+1$且$a_i=b_j$，则该位置是由“都选”情况转移而来，即$a_i$、$b_j$都属于公共子序列，两个相等故输出其中一个即可
      • $i$、$j$位置字符已选，均向前移动1位
   3. 如果$f(i,j)=f(i-1,j)$，则该位置是由“选$j$不选$i$”情况转移而来，$a_i$不选，等同于只考虑到$a_{i-1}$，$i$向前移动1位
   4. 如果$f(i,j)=f(i,j-1)$，同上，$i$、$j$调换而已

更个新 代码里面逆推时没有做额外处理 所以输出的其实是公共序列的逆序

代码

import java.util.*;
import java.lang.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);

    static int n, m;
    static int[][] f = new int[1010][1010];

    public static void main(String[] args) {
        n = scanner.nextInt();
        m = scanner.nextInt();
        char[] a = (" " + scanner.next()).toCharArray();
        char[] b = (" " + scanner.next()).toCharArray();
        // 遍历a、b字符，推导最长公共子序列
        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]);  // f(i,j) = max(f(i-1,j), f(i,j-1))
                if (a[i] == b[j]) {  // 当且仅当a[i]=b[j]时 公共子序列长度+1
                    f[i][j] = Math.max(f[i][j], f[i - 1][j - 1] + 1);
                }
            }
        }
        System.out.println(f[n][m]);
        // 逆推具体方案
        for (int i = n, j = m; i >= 1 && j >= 1; ) {  // a[i] b[j]
            if (a[i] == b[j] && f[i][j] == f[i - 1][j - 1] + 1) {  // 如果属于公共子序列
                System.out.print(a[i] + " ");
                i--;
                j--;
            } else if (f[i][j] == f[i - 1][j]) {  // 如果由选j不选i的情况转移而来
                i--;
            } else if (f[i][j] == f[i][j - 1]) {  // 如果由选i不选j的情况转移而来
                j--;
            }
        }
        System.out.println();
    }
}

DP算法二

受AcWing 272. 最长公共上升子序列（Java DP + 时间优化 + 空间优化）启发，发现这个思路也可以用，时间空间优化方法相同

1. $f(i,j)$表示“只考虑数组$a$的前$i$个和数组$b$的前$j$个且公共序列以$b_j$结尾的选法集合”，属性：公共子序列长度$Max$
2. 状态计算，对每个$a_i$，枚举公共子序列以$b_j$结尾的情况，讨论$a_i$是否可选
   • $a_i \neq b_j$，不选，状态从上层转移，$f(i,j) = f(i-1,j)$
   • $a_i = b_j$，可选
     • 起码可以自成一个序列，则长度为1
     • 求$f(i-1, 1 \cdots j-1)_{max}$找到该位置前已记录的最长公共子序列，即“只考虑数组$a$的前$i-1$个和数组$b$的前$k$个且以$b_k$结尾的最长公共序列长度”，该序列与$a_i$相接组成更长的序列，此时$f(i,j) = f(i-1, 1 \cdots j-1)_{max} + 1$
   • 综上：$f(i,j) = max(f(i-1,j), 1,f(i-1, 1 \cdots j-1)_{max} + 1)$
3. 最后需要遍历一次$f(n,1 \cdots m)$取最大长度

代码

import java.util.*;
import java.lang.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);
    static int n, m;
    static int[][] f = new int[1010][1010];

    public static void main(String[] args) {
        n = scanner.nextInt();
        m = scanner.nextInt();
        char[] a = (" " + scanner.next()).toCharArray();
        char[] b = (" " + scanner.next()).toCharArray();
        for (int i = 1; i <= n; i++) {
            int maxv = 0;  // 记录 f(i-1, 1···j-1)的最大值
            for (int j = 1; j <= m; j++) {
                f[i][j] = f[i - 1][j];
                if (a[i] == b[j]) {
                    f[i][j] = Math.max(f[i][j], maxv + 1);
                }
                maxv = Math.max(maxv, f[i - 1][j]);  // 更新前置位最大长度
            }
        }
        int ans = 0;
        for (int i = 1; i <= m; i++) {
            ans = Math.max(ans, f[n][i]);
        }
        System.out.println(ans);
    }
}