LeetCode Longest Palindromic Subsequence Given a string s, find the longest palindromic subsequence’s length in s. You may assume that the maximum length of s is 1000. Example 1: Input:
"bbbab"Output:
4One possible longest palindromic subsequence is “bbbb”. Example 2: Input:
"cbbd"Output:
2One possible longest palindromic subsequence is “bb”.
求一个字符串的最长回文子序列。 使用DP求解，假设dp[i][j]表示原字符串范围[i,j]中的最长回文子序列的长度。则如果s[i]==s[j]，则dp[i][j]=dp[i+1][j-1]+2，即是临近内层的最长回文子序列长度加2。如果s[i]!=s[j]，则dp[i][j]=max(dp[i][j-1],dp[i+1][j])，即是左端或者右端最长回文子序列长度的最大值。 初始时dp[i][i]=1，即单个字符自成回文，长度为1。 代码如下： [cpp] class Solution2 { public: int longestPalindromeSubseq(string s) { int n = s.size(); vector<vector<int>> dp(n, vector<int>(n, 0)); for (int i = n – 1; i >= 0; –i) { dp[i][i] = 1; for (int j = i + 1; j < n; ++j) { if (s[i] == s[j])dp[i][j] = dp[i + 1][j – 1] + 2; else dp[i][j] = max(dp[i][j – 1], dp[i + 1][j]); } } return dp[0][n – 1]; } }; [/cpp] 本代码提交AC，用时68MS。 上述计算有些区间会重复计算dp[i][j]，可以用递归方法求解，并且把计算过的值记录下来，下次遇到查询时直接返回。代码如下： [cpp] class Solution { private: int helper(int l, int r, const string &s, vector<vector<int>> &dp) { if (l > r)return 0; if (l == r)return 1; if (dp[l][r] != 0)return dp[l][r]; if (s[l] == s[r])dp[l][r] = helper(l + 1, r – 1, s, dp) + 2; else dp[l][r] = max(helper(l, r – 1, s, dp), helper(l + 1, r, s, dp)); return dp[l][r]; } public: int longestPalindromeSubseq(string s) { int n = s.size(); vector<vector<int>> dp(n, vector<int>(n, 0)); return helper(0, n – 1, s, dp); } }; [/cpp] 本代码提交AC，用时49MS。 参考：https://discuss.leetcode.com/topic/78603/straight-forward-java-dp-solution/2]]>
贪心的代码如下：
[cpp]
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int n = nums.size();
if (n < 2)return n;
int ans = 1, i = 0, j = 1;
bool up = false;
while (j < n && nums[j] == nums[i])++j;
if (nums[j] > nums[i])up = true;
else up = false;
while (j < n) {
if (nums[j] > nums[i] && up) {
++ans;
up = false;
while (j + 1 < n&&nums[j + 1] >= nums[j])++j;
}
else if (nums[j] < nums[i] && !up) {
++ans;
up = true;
while (j + 1 < n&&nums[j + 1] <= nums[j])++j;
}
i = j++;
}
return ans;
}
};
[/cpp]
本代码提交AC，用时3MS。
还可以用动态规划的方法，假设up[i]表示第i个元素处于抖动序列的最后一个位置，且是上升的趋势时，前[0,i]的抖动子序列的最大长度。类似的，down[i]表示第i个元素处于抖动序列的最后一个位置，且是下降趋势时，前[0,i]的抖动子序列的最大长度。
则对于第i个元素，可以枚举所有i前面的元素j跳到i，如果nums[i]>nums[j]，则i处于抖动序列的上升末尾，则从j到i构成的抖动序列中，j是处于下降趋势的，所以有up[i]=max(up[i],down[j]+1)。类似的，如果nums[i]<nums[j]，则有down[i]=max(down[i],up[j]+1)。最后返回1+max(up[n-1],down[n-1])。
代码如下：
[cpp]
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int n = nums.size();
if (n < 2)return n;
vector<int> up(n, 0), down(n, 0);
for (int i = 1; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (nums[i] > nums[j])up[i] = max(up[i], down[j] + 1);
else if (nums[i] < nums[j])down[i] = max(down[i], up[j] + 1);
}
}
return 1 + max(up[n – 1], down[n – 1]);
}
};
[/cpp]
本代码提交AC，用时6MS。
可以对上述代码优化。j无需枚举所有i前面的元素，而是i直接根据和前一个元素i-1的大小关系进行更新。如果nums[i]>nums[i-1]，则i处于上升末端，所以i-1必须处于下降末端，有up[i]=down[i-1]+1，down[i]不变，即down[i]=down[i-1]。如果nums[i]<nums[i-1]，则i处于下降末端，所以i-1必须处于上升末端，有down[i]=up[i-1]+1，up[i]不变，即up[i]=up[i-1]。如果nums[i]==nums[i-1]，则up[i]和down[i]都不变，分别等于up[i-1]和down[i-1]。
为什么这里可以不用枚举所有i前面的元素了呢，因为上述三种情况中，只更新了该更新的，不能更新的情况都等于前一个元素的结果了，比如第一种情况更新了up[i]，则down[i]保持了down[i-1]的值，所以后续如果要用到down[i-1]的值，也可以直接用down[i]的值了。
代码如下：
[cpp]
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int n = nums.size();
if (n < 2)return n;
vector<int> up(n, 0), down(n, 0);
up[0] = down[0] = 1;
for (int i = 1; i < n; ++i) {
if (nums[i] > nums[i – 1]) {
up[i] = down[i – 1] + 1;
down[i] = down[i – 1];
}
else if (nums[i] < nums[i – 1]) {
down[i] = up[i – 1] + 1;
up[i] = up[i – 1];
}
else {
up[i] = up[i – 1];
down[i] = down[i – 1];
}
}
return max(up[n – 1], down[n – 1]);
}
};
[/cpp]
本代码提交AC，用时3MS。
还可以对上述代码进行空间的优化，因为up[i]和down[i]都只用到了前一个结果up[i-1]和down[i-1]，所以只需保留前一个结果就行，不需要两个数组。代码如下：
[cpp]
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int n = nums.size();
if (n < 2)return n;
int up = 1, down = 1;
for (int i = 1; i < n; ++i) {
if (nums[i] > nums[i – 1]) {
up = down + 1;
}
else if (nums[i] < nums[i – 1]) {
down = up + 1;
}
}
return max(up, down);
}
};
[/cpp]
本代码提交AC，用时0MS，是效率最好的一种解法了。
参考：