[数据结构与算法]动态规划——最长回文子序列

题目简略如下：

给出一个字符串s，求s中的最长回文子序列的长度。

例如：在absbzaz中，最长的回文子序列就是absba，长度为5

如上图所示：此时的dp数组应该分情况讨论了：

最简单的一种情况：当s[i]==s[j]时，此时最大回文序列应该==dp[i+1][j-1]+2==dp[i][j]

另外情况下：?当s[i]！=s[j]时，dp[i][j]应该取决于dp[i][j-1]跟dp[i+1][j]哪个更大

这样的话状态转移方程遍出来了。

这边先给出实现代码：

string s;
    cin>>s;
    int length = s.size();
    cout<<length<<endl;
    //int dp[length][length];
    vector<vector<int> > dp(length, vector<int>(length, 0));//初始化数组
    for (int k = 0; k < length; k++) //一个字符就是一个回文串
        dp[k][k] = 1;

    for( int i=length-1;i>=0;i--)
    {
        for( int j=i+1;j<length;j++)
        {
            if(s[i]==s[j])
               dp[i][j]=dp[i+1][j-1]+2;
            else
            {
                dp[i][j]=max(dp[i+1][j],dp[i][j-1]);
            }
        }
    }

    cout<<dp[0][length-1];

?OK然后我们来解决代码中比较疑惑的地方：

① 首先dp数组是一个length*length的一个二维数组：然后我们要对其赋初值，可知i是一定要小于j的（可以想象为i为队头指针，j为队尾指针），当i>j的时候dp数组的值为0（子序列不存在当然为0） 当i==j的时候，也就是i j指向同一个字符，dp赋值为1（一个字符本数就是回文）

② 然后比较ex的就是数组遍历的方向了：这边打字不太好说明，我就拿笔写下来了：

?

?

?

。