总结

DP总结
1.为什么采用f[i][j]而不是f[i]：本题之所以采用f[i][j],是有必然性的，不妨试想，f[i]能否合理的表示集合的状态，会发现无论如何描述，仅有一个变量i，只能描述A或者B的单个状态，但这样分析集合的话，就违反了不重不漏的原则。

2.如何合理的进行状态表示：本题的状态表示的集合定义为 - f[i][j] (表示以A[1 ~ i] 和 B[1 ~ j] 中的公共子序列的集合)。这样的表示类同于01背包问题中的f[i][j] (表示存放至多i个物品，价值的最大值的集合)。很容易发现，这两个f[i][j]统计的都是一段区间，范围内的集合，例如f[2][3],肯定也包含f[2][2],f[2][1],f[1][2],f[1][1]…。于是乎，就衍生出了我们对于属性的处理。

问你如何寻找最大值，知道f[i][j]是集合之后，便只需要对f[i][j]与其要取出的上一轮的f[I][J]寻求帮助了，也就是说，f[i][j]是近视眼，只用看离他10米近的小石子，而不用看远处的高山了。而个人认为这也是DP问题的一个核心-状态计算（状态转移方程）的核心。故而找出第一个不同的元素就是解决状态计算的关键了。

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

public class Main
{

    static final int N = 1010;
    static int ans;

    static char[] a = new char[N], b = new char[N];
    static int[][] f = new int[N][N];

    public static void main(String args[]) throws IOException
    {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter log = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
        String[] T = in.readLine().split("\\s+");
        int n = Integer.parseInt(T[0]),m = Integer.parseInt(T[1]);

        String A = in.readLine();
        for(int i = 1; i <= n; i++) a[i] = A.charAt(i - 1);
        String B = in.readLine();
        for(int i = 1; i <= m; i++) b[i] = B.charAt(i - 1);

        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[i] == b[j]) f[i][j] = Math.max(f[i][j],f[i - 1][j - 1] + 1);
            }
        }

        log.println(f[n][m]);
        log.flush();
    }
}