public class Solution {
/**
* @param A, B: Two string.
* @return: the length of the longest common substring.
*/
public int longestCommonSubsequence(String A, String B) {
int lenA = A.length();
int lenB = B.length();
if(lenA==0 || lenB==0){
return 0;
}
int [][] result = new int[lenA+1][lenB+1];
int maxResult = -1;
for(int i=0;i<lenA+1;i++){
for(int j=0;j<lenB+1;j++){
result[i][j] = 0;
}
}
for(int i=1;i<=lenA;i++){
for(int j=1;j<=lenB;j++){
if(A.charAt(i-1) == B.charAt(j-1)){
result[i][j] = result[i-1][j-1]+1;
}else{
result[i][j] = max(result[i-1][j],result[i][j-1]);
}
maxResult = max(result[i][j],maxResult);
}
}
return maxResult;
}
public int max(int src,int dst){
if(src > dst){
return src;
}else{
return dst;
}
}
}
思路:
经典dp
(1)找状态,从后到前,目标:result[i][j]表示,A[i]与B[j]的最长公共子序列(i<=n,j<=m)。
(2)确定状态转移方程,二种决策(a[i] b[i]一样, a[i] b[i]不一样)
(3)复杂度为O(lenA*lenB),此种解法为递推,从前到后,使用循环来写。
(4)还有一种解法是递归,从后到前,记忆化搜索(备忘录)
(5)边界条件是遇到0