公共子序列（动态规划）

给定两个字符串A和B，长度分别为m和n，要求找出它们最长的公共子序列，并返回其长度。例如：
A = “HelloWorld”
B = “loop”
则A与B的最长公共子序列为 “loo”,返回的长度为3。

importjava.util.*;publicclassQue31{publicstaticintLCS(char[]a,char[]b){int[][]dp=newint[a.length+1][b.length+1];for(inti=1;i<=a.length;i++){for(intj=1;j<=b.length;j++){if(a[i-1]==b[j-1]){dp[i][j]=dp[i-1][j-1]+1;}else{dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);}}}returndp[a.length][b.length];}publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);Stringstr1=sc.next();Stringstr2=sc.next();char[]a=str1.toCharArray();char[]b=str2.toCharArray();System.out.println(LCS(a,b));sc.close();}}