最长公共子序列（LCS）

递推版

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        while(cin.hasNext()) {
            int[][] dp = new int[1000][1000];
            String s1,s2;
            s1 = cin.next();
            s2 = cin.next();
            int len1 = s1.length();
            int len2 = s2.length();
            for(int i = 0;i < len1;i++) {
                for(int j = 0;j < len2;j++) {
                    if(s1.charAt(i) == s2.charAt(j))
                        dp[i + 1][j + 1] = dp[i][j] + 1;
                    else 
                        dp[i + 1][j + 1] = Math.max(dp[i + 1][j],dp[i][j + 1]);
                }
            }
            System.out.println(dp[len1][len2]);
        }
    }
}

递归版

import java.util.Scanner;
public class Main {
    public static int[][] res = new int[1000][1000];
    public static String s1,s2;
    public static int len1,len2;
    public static int dp(int i,int j) {
        if(i >= len1 || j >= len2)
            return 0;
        if(res[i][j] > 0)
            return res[i][j];
        if(s1.charAt(i) == s2.charAt(j))
            return res[i + 1][j + 1] = dp(i + 1,j + 1) + 1;
        int a = dp(i + 1,j);
        int b = dp(i,j + 1);
        return res[i + 1][j + 1] = Math.max(a,b);
    }
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        while(cin.hasNext()) {
            s1 = cin.next();
            s2 = cin.next();
            len1 = s1.length();
            len2 = s2.length();
            for(int i = 0;i < len1;i++)
                for(int j = 0;j < len2;j++)
                    res[i][j] = 0;
            System.out.println(dp(0,0));
        }
    }
}