三、动态规划（1）-最长公共子序列（ POJ1458)

需要找到每个公共字符顺序相同的序列即可。

#include <iostream>
#include<algorithm>
#include<string>
using namespace std;

string s1;
string s2;
//数组保存
int maxLen[100][100];

int main(){
    cout << "输入两个字符串,空格分开：";
    while (cin >> s1 >> s2){
        int len1 = s1.length();
        int len2 = s2.length();
        int n;
        int i, j; 
        //初始化
        for (i = 0; i <= len1; ++i)
            maxLen[i][0] = 0;
        for (j = 0; j <=len2; ++j)
            maxLen[0][j] = 0;

        for (i = 1; i <=len1; ++i)
        {
            for (j = 1; j <= len2; ++j)
            {
                if (s1[i - 1] == s2[j - 1])
                    maxLen[i][j] = maxLen[i - 1][j - 1] + 1;
                else{
                    maxLen[i][j] = max(maxLen[i - 1][j], maxLen[i][j - 1]);
                }
            }
        }
        cout << "最长子序列长度： "<<maxLen[len1][len2] << endl;
        for (i = 0; i <= len1; ++i)
        {
            for (j = 0; j <= len2; ++j)
                cout << " " << maxLen[i][j] << " ";
            cout << endl;
        }
    }
    return 0;

}