去哪儿2018校招在线考试-编程题二

题目 逆序字符串的最长公共子序列长度

描述

同学们，我们刚刚经历了十一和中秋双节假期，
让我们一起预祝我们的祖国繁荣富强，同学们每个中秋与家人共赏明月，
也期待同学们能够加入去哪儿网，为大家的出游和回家团圆尽一份力量。
我们的第二题是这样的，给出一个以空格作为分隔符的字符串，
求其与其空格分隔的逆序字符串的最长公共子序列长度。

输入

例如：输入 2017 11 02
其逆序字符串为 02 11 2017

输出

6(2 11 2)

Example

Input

2017 11 02

Output

6

题解

动态规划

• 常见的题型不多说
• 时间复杂度 O(n^2),空间复杂度 O(n)

#include <bits/stdc++.h>

#define ll long long
using namespace std;

string str1,str2;

int main()
{
    getline(cin,str1);

    stringstream ss(str1);

    string tmp;

    ss>>tmp;
    str2=tmp.append(str2);
    while(ss>>tmp)
    {
        str2=tmp.append(" ").append(str2);
    }

    int len=str1.length();
    int res[len+5];
    memset(res,0,sizeof res);

    int maxLen=0;

    for(int i=0;i<len;++i)
    {
        for(int j=0;j<len;++j)
        {
            if(str1[i]==str2[j])
            {
                res[j+1]=res[j]+1;
                maxLen=max(maxLen,res[j+1]);
            }
            else
            {
                res[j+1]=max(res[j],res[j+1]);
            }
        }
    }
    cout<<maxLen;
}