Longest Common Subsequence

来源：nineChapter

原帖：nineChapter; dp

题目：
state: f[i][j]表示前i个字符配上前j个字符的LCS的长度
function: f[i][j] = f[i-1][j-1] + 1 // a[i] == b[j]
                 = MAX(f[i-1][j], f[i][j-1]) // a[i] != b[j]
intialize: f[i][0] = 0
               f[0][j] = 0
answer: f[a.length()][b.length()]

代码：

 int longestCommonSubsequence(string s1, string s2) {  
   int M = s1.size(), N = s2.size();  
   int dp[M + 1][N + 1] = {0};  
   //memset(dp, 0, sizeof(dp));  
   for (int i = 0; i <= M; ++i) {  
     dp[i][0] = 0;  
   }  
     
   for (int j = 0; j <= N; ++j) {  
     dp[0][j] = 0;  
   }  
   for (int i = 1; i <= M; ++i) {  
     for (int j = 1; j <= N; ++j) {  
       if (s1[i - 1] == s2[j - 1]) {  
         dp[i][j] = dp[i - 1][j - 1] + 1;  
       } else {  
         dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);  
       }  
     }  
   }  
   return dp[M][N];  
 }