（注意：我发现最长回文子序列(Longest Palindromic Subsequence)问题与最长回文子串(Longest Palindromic Substring)不一样，子序列不要求下标一定连续的，但子串下标一定是连续递增的，《算法导论》中要求的是最长回文子序列，所以与LeetCode-Longest Palindromic Substring不同，这里我做的是书中的问题）
这里对最优子结构和算法参考思路：
http://blog.csdn.net/u012243115/article/details/41010913
代码：
#include "stdafx.h"
#include <iostream>
#include <vector>
#include <string>
#include <minmax.h> class Solution {
public:
int LongestPalindromicSubsequence(std::string s)
{
if (s.empty())
return 0; std::vector<std::vector<int> > dp(s.size(), std::vector<int>(s.size()));
int LPSLength = 1;
for (int i = s.size() - 1; i >= 0; i--)
{
dp[i][i] = 1;
for (int j = i + 1; j < s.size(); 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]);
LPSLength = max(LPSLength, dp[i][j]);
}
}
return LPSLength;
}
}; int main()
{
std::vector<std::string> strs = { "character","inileveltnt","bilibili","abcef","rever" }; for (auto s : strs)
{
std::cout << "字符串:" << s << std::endl;
std::cout << "结果:" << Solution().LongestPalindromicSubsequence(s) << std::endl;
} getchar();
return 0;
}
LeetCode上的提交详情：
改成这样就提高到了51ms:
class Solution {
public:
int longestPalindromeSubseq(string s) {
if (s.empty())
return 0;
vector<vector<int> > dp(s.size(), vector<int>(s.size()));
for (int i = s.size() - 1; i >= 0; i--)
{
dp[i][i] = 1;
for (int j = i + 1; j < s.size(); 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]);
}
}
return dp[0][s.size() - 1];
}
};
提交详情：
还有更快的22ms的解决方案：
class Solution {
public:
int longestPalindromeSubseq(string s) {
if (s.size() == 0) return 0;
vector<int> dp(s.size(), 0);
for (int i = s.size() - 1; i >=0; i--) {
int prev = 1;
for (int j = i + 1; j < s.size(); j++) {
int curr;
if (s[i] == s[j]) curr = 2 + dp[j - 1];
else curr = max(prev, dp[j]);
dp[j - 1] = prev;
prev = curr;
}
dp[s.size() - 1] = prev;
}
return dp[s.size() -1];
}
};
也是dp思路，但空间复杂度优化为O(n)。