求两字符串最长公共子序列 - c++编程基础

这是动态规划法的典型题目，长度为row和长度为col的两个串，如何求他们的最长公共子序列。这个子序列是可以不连续的。

方法：

1 建立(row+1)*(col+1)的二维表,

2. 初始化其首行首列为零

3. 以m串为行，n串为列，那么可以逐行填写。第一行代表n串的第一个字符和m串比较，第二行代表n串的第一和第二个字符都和m串比较，以此类推。

4. 如果是相同字符，那么就把[m-1][n-1]+1和[m-1[n]和[m][n-1]比较，填入大数。

5. 如此反复填完表，就可以得到最终结果[m][n]

很难一下子说清楚，这里就弥补一下一般书上都没有的C++程序吧：

#include  
#include  
#include  
  
using namespace std;  
  
class Solution {  
public:  
    int longestSub(string sa, string sb)  
    {  
        int row = sa.size();  
        int col = sb.size();  
        vector




 > dArray;  
        vector rowV(col+1,0);  
        for(int i = 0; i