http://www.lintcode.com/en/problem/longest-common-subsequence/
http://www.jiuzhang.com/solutions/longest-common-subsequence/
- 状态定义：dp[i][j] 为 str2 前 i 个字符，对应 str1 前 j 个字符，所产生的 longest common sequence size
- 状态转移方程：
dp[i][j] = dp[i - 1][j - 1] if str2[i] == str1[j]
dp[i][j] = max(dp[i - 1][j, dp[i]][j - 1]) if str2[i] != str1[j]
- 初始化：
dp[0][j] 为 0；dp[i][0] 为 0;
int[][] dp = new int[len2 + 1][len1 + 1]；
- 循环体：双循环
- 返回 target：dp[len1][len2]
From 九章：
state: f[i][j]表示前i个字符配上前j个字符的LCS的长度 function: f[i][j] = f[i-1][j-1] + 1 // a[i] == b[j]
= MAX(f[i-1][j], f[i][j-1]) // a[i] != b[j]
intialize: f[i][0] = 0， f[0][j] = 0
answer: f[a.length()][b.length()]
public int longestCommonSubsequence(String A, String B) {
int n = A.length();
int m = B.length();
int f[][] = new int[n + 1][m + 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.charAt(i - 1) == B.charAt(j - 1))
f[i][j] = f[i - 1][j - 1] + 1;
}
}
return f[n][m];
}
