Longest common subsequence - dynamic programming

LongestCommonSubsequence.cpp

/*
最长公共子序列（不连续） LCS　　Longest Common Subsequence
找两个字符串的最长公共子串，这个子串要求在原字符串中是连续的。而最长公共子序列则并不要求连续。

cnblogs与belong，最长公共子序列为blog（cnblogs, belong），最长公共子串为lo（cnblogs, belong）

这两个问题都是用空间换空间，创建一个二维数组来记录之前的每个状态

http://blog.csdn.net/yuxin6866/article/details/52507623

参考：【动态规划】最长公共子序列与最长公共子串
http://www.cnblogs.com/en-heng/p/3963803.html

C++实现最长公共子序列和最长公共子串
http://blog.csdn.net/chengonghao/article/details/51913108
状态转移方程：

用i，j遍历两个子串x,y，如果两个元素相等就 +1 ，不等就用上一个状态最大的元素

Formula can be looked up through the blog:

http://blog.csdn.net/yuxin6866/article/details/52507623

*/
public static int lcs(String str1, String str2) 
{
      int len1 = str1.length();
      int len2 = str2.length();
      int c[][] = new int[len1+1][len2+1];
      for (int i = 0; i <= len1; i++) 
      {
          for( int j = 0; j <= len2; j++) 
          {
              if(i == 0 || j == 0) 
              {
                  c[i][j] = 0;
              } 
              else if (str1.charAt(i-1) == str2.charAt(j-1)) 
              {
                 c[i][j] = c[i-1][j-1] + 1;
              } 
              else 
              {
                 c[i][j] = max(c[i - 1][j], c[i][j - 1]);
             }
         }
     }
     
     return c[len1][len2];
}