【每日编程-78期】南京理工大学上机题(三)

输入格式：

手动输入字符串

输出格式：

输出最长回文子序列长度

输入样例：

abcbab

输出样例：

5

解决方法：

（1）算法的基本思想：

对任意字符串，如果头和尾相同，那么它的最长回文子序列一定是去头去尾之后的部分的最长回文子序列加上头和尾。如果头和尾不同，那么它的最长回文子序列是去头的部分的最长回文子序列和去尾的部分的最长回文子序列的较长的那一个。

（2）代码实现：

#include#includeusingnamespacestd;intlongestPalindromeSubSequence1(string str){int n = str.length();vector<vector<int>> dp(n, vector<int>(n));for (int j = 0; j < n; j++)    {        dp[j][j] = 1;for (int i = j - 1; i >= 0; i--)        {if (str[i] == str[j])                dp[i][j] = dp[i + 1][j - 1] + 2;else                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);        }    }return dp[0][n - 1];}intlongestPalindromeSubSequence2(string str){int n = str.length();vector<vector<int>> dp(n, vector<int>(n));for (int i = n - 1; i >= 0; i--)    {        dp[i][i] = 1;for (int j = i + 1; j < n; j++)        {if (str[i] == str[j])                dp[i][j] = dp[i + 1][j - 1] + 2;else                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);        }    }return dp[0][n - 1];}intmain(){string s;int length;while (cin >> s)    {        length = longestPalindromeSubSequence2(s);cout << length << endl;    }return0;}

输入格式：

输出格式：

输入样例：

5 5 51 1 3 32 2 0 42 4 2 53 3 1 45 3 0 33

输出样例：

[5,0][2,0][0,4]