[数据结构与算法]最长公共子序列（LCS）

**

动态规划都是从最小状态到最大状态的过程，我们可以先匹配两个字符串的一个字符，再到两个字符，三个字符

。。。
我们可以使用二维数组去装 字符串a的下标0到下标i 和 字符串a的下标0到下标j 之间的公共子序列的最大值
值得注意的是下标i与下标j指0到该下标而不是单单此下标
例如abbbbbbb 与 acccccc
当i = 0,b = 6;
则是a 与 acccccc匹配，结果为一，那么当i=1时,ab与acccccc匹配则取决于 a与acccccc和 ac与accccc 画个二维表就理解了
而自小而大来看:
比如字符串a: abcb 与字符串b: bdc相匹配时:
当此时i = 3,b = 2 那么我们将b和c进行比较可以发现不相等，则其最大子序列取决于a中abc 和bdc匹配 与abcd 与bd相匹配的最大值
而abc与bdc匹配的结果显然等于ab 与bd的匹配结果+1（实际上也相当于ab和bdc匹配 与 abc和bd匹配 两者间的最大值）**
例如
“abcde”
“ace”
有

而结果自然便是dp[len_a][len_b]
代码

class Solution {
public:
    int longestCommonSubsequence(string a, string b) {
int len_a = a.length(),len_b = b.length();
a="#"+a;
b="#"+b;
int dp[len_a+1][len_b+1];
//初始化
for(int i=0;i<=len_a;i++)
dp[i][0] = 0;
for(int i=0;i<=len_b;i++)
dp[0][i] = 0;
//循环查找

for(int i=1;i<=len_a;i++)
{
  for(int j=1;j<=len_b;j++)
  {
    if(a[i]==b[j])
    dp[i][j] =dp[i-1][j-1]+1;
    else if(a[i]!=b[j])
      dp[i][j] = max (dp[i-1][j],dp[i][j-1]);
  }
}

return dp[len_a][len_b];
    }
};