题目描述：

 链接：https://www.nowcoder.com/questionTerminal/9ae56e5bdf4f480387df781671db5172?answerType=1&f=discussion

来源：牛客网

我们有两个字符串m和n，如果它们的子串a和b内容相同，则称a和b是m和n的公共子序列。子串中的字符不一定在原字符串中连续。

例如字符串“abcfbc”和“abfcab”，其中“abc”同时出现在两个字符串中，因此“abc”是它们的公共子序列。此外，“ab”、“af”等都是它们的字串。

现在给你两个任意字符串（不包含空格），请帮忙计算它们的最长公共子序列的长度。

输入包含多组数据。

每组数据包含两个字符串m和n，它们仅包含字母，并且长度不超过1024。

对应每组输入，输出最长公共子序列的长度。

abcfbc abfcab
programming contest
abcd mnp

4
2
0

思路讲解：

       要求从两个字符串中，找到最长的子序列，这两个子序列不一定是连续的。 以题目中这两个字符串举例， abcfbc  abfcab ，公共子序列有 a，ab，abc，af ，abcb等，但最长的只有abcb，我们通过肉眼能很容易的看出来，abcb
是符合题意的最长公共子序列，找出这个子序列，我们潜意识的排除了 顺序不对的公共项（就是没有把 abcf 和 abfc 视为符合题意的子序列），排除了字符比较时，相同的字符被重复计算的问题， 也没有因为中间有间隔，
就把abc 视为最长公共子序列。

    但程序中要让它排除这些问题， 常规的方法很麻烦而且很难，于是我们采用 动规思想，就是让一个字符串中的每一个字符去 和 另一个字符串中的每一个字符进行比较，如果相同就给次数加 一 ？ 不，这样就会出现我前面提到的
问题，相同的字符被重复比较，比如 abcfbc  中的 字符 a 在与 abfcab 比较时，会被计算两次。那为了避免这个问题，我们就看它们的前一位，在它们前一位的基础上进行加一。  具体看下图，再进一步解释。

   根据图来继续进行讲解，因为不能两个字符一相等，就给公共子序列个数加一，我们要看它们的前面一个，所以为了在第一个字符进行比较时有所参考，我们给要比较的两个字符串前面加一个空字符，空字符和谁比较都是0，

这里没有问题吧。 然后具体讲解这个记录两个字符比较的二维数组（arr[ ][ ]）如何进行。 还是以 abfcab   和   abcfbc为例， 刚开始用  abfcab 的 a字符 和  abcfbc 的每一个字符进行比较，和它里面的a相同，先看它们的前面一位，

都是空，也就是arr[0][0] =0 (初始化后默认为0) ，那么此刻的公共子序列长度为 0+1 =1， 然后继续用 a 比较abcfbc 里的 b，不相同，不相同就看 a前面的空字符与 abcfbc 的ab比较结果是0， 再看 a与  abcfbc 中b前面的字符

（也就是a）比较结果是1， 所以  abfcab 中的a 与 abcfbc 中的b 公共字符串长度应该是1（取两者的最大值），因为abfcab 中的a  与 abcfbc 中的b（其实是ab）确实有一个相同的字符。  abfcab 中的a 继续与 abcfbc 中的

   c,f,b,c 比较结果都是1。  

       然后，abfcab 中的 b 与 abcfbc 每一个字符进行比较， 比到b时，看它们前一位 也就是arr[1][1] 是1，所以此时的公共子序列长度为 1+1 =2 ，然后继续比较 比到  abcfbc 的第二个b时，看它们的前面一个 也就是arr[1][4],

结果是1，所以这里的公共子序列是2，而不是3。 为什么总要看前一个，因为 abfcab 中b 的前一个是a ，a与 abcfbc整个比较完也确实只有一个相等（这里不要误解，a与 abcbaaa 比较也只有一个相等）。 我们通过看前一个，

就能避免重复的问题。  所以这样就能得到，大家看着有点头疼的 动规规划状态方程， 

若str1[ i ] == str2[ j ]，则 arr[ i ][ j ]  = max( dp[ i-1 ][ j ],  dp[ i ][ j-1 ],  dp[ i-1 ][ j-1 ]+1 )   

若str1[ i ] != str2[ j ]，则 dp[ i ][ j ] = max( dp[ i-1 ][ j ],  dp[ i ][ j-1 ] )  现在看它，应该好理解多了吧 ！  

 

代码解释

// write your code here
import java.util.*;
public class Main{
 public static void main(String[] args){
    Scanner scan = new Scanner(System.in);
     while(scan.hasNext()){
         String m = scan.next();
         String n =scan.next();
         int lenM = m.length();
         int lenN = n.length();
                 // 我们需要给字符串前面加空格，便于后面的字符串比较，所以大小设为 lenM+1和lenN+1 
         int[][] arr = new int[lenM+1][lenN+1];
         for(int i=1;i<= lenM;i++){
             for(int j=1;j<= lenN;j++){
                              // 依次比较两个字符串的每一个字符，但要注意是字符串，要用charAt()函数获取每个字符
                 if(m.charAt(i-1)== n.charAt(j-1)){
                           // 这里就是运用上面的状态方程
                     arr[i][j]= arr[i-1][j-1]+1;
                 }else{
                     arr[i][j]=Math.max(arr[i-1][j],arr[i][j-1]);
                 }
             }
         }
               //  最后为什么要打印这个值，有上面图可以看出 比较结果为4 的位置有多个， 这里是因为，只有arr[lenM][lenN]处的数值，才能代表是两个字符串wan'zhen          System.out.println(arr[lenM][lenN]);
         
     }
     
   }   
}