公共子序列（动态规划）
给定两个字符串A和B长度分别为m和n要求找出它们最长的公共子序列并返回其长度。例如A “HelloWorld”B “loop”则A与B的最长公共子序列为 “loo”,返回的长度为3。importjava.util.*;publicclassQue31{publicstaticintLCS(char[]a,char[]b){int[][]dpnewint[a.length1][b.length1];for(inti1;ia.length;i){for(intj1;jb.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){ScannerscnewScanner(System.in);Stringstr1sc.next();Stringstr2sc.next();char[]astr1.toCharArray();char[]bstr2.toCharArray();System.out.println(LCS(a,b));sc.close();}}
