0516. Longest Palindromic Subsequence ===================================== 题目信息 -------- :题号: 0516 :难度: Medium :主题: 字符串、子序列、回文、最大长度 :原题: `LeetCode 0516 `_ :重点: 子序列可以删除字符但不能改变剩余顺序、无需连续、返回长度而不是具体字符串 题目重述 -------- 给定只含小写英文字母的字符串 ``s``,从中删除任意数量的字符但保持剩余字符的相对顺序,可以得到一个子序列。返回所有回文子序列中的最大长度。 回文要求从左到右和从右到左读取相同。子序列不要求在原字符串中连续;单个字符本身也是长度为 1 的回文子序列。 自建示例 -------- 删除中间不匹配字符: .. code-block:: text 输入:s = "agbdba" 输出:5 解释:可以保留子序列 "abdba",它是长度为 5 的回文;不存在更长的回文子序列。 没有相同字符: .. code-block:: text 输入:s = "abc" 输出:1 解释:任意单个字符都构成回文,但无法选择两个或更多字符组成回文。 区间回文状态压缩 ---------------- 令区间 ``[i,j]`` 的状态表示该子串能得到的最长回文子序列长度。若两端字符相同,可以把它们同时选入,状态为内层 ``[i+1,j-1]`` 加 2;若不同,则最优解必须放弃左端或右端之一,取两个较短区间的较大值。 用一维数组按 ``i`` 从右向左处理。更新 ``dp[j]`` 前保存旧的 ``dp[j-1]``,它就是上一轮的内层状态,避免覆盖二维转移所需的信息。 C++ 实现 -------- .. code-block:: cpp class Solution { public: int longestPalindromeSubseq(std::string s) { int n = static_cast(s.size()); std::vector dp(n, 1); for (int left = n - 2; left >= 0; --left) { int diagonal = 0; for (int right = left + 1; right < n; ++right) { int old = dp[right]; if (s[left] == s[right]) { dp[right] = diagonal + 2; } else { dp[right] = std::max(dp[right], dp[right - 1]); } diagonal = old; } } return dp.empty() ? 0 : dp.back(); } }; 代码分析 -------- 相等端点的选择和不相等端点的二选一完整覆盖了区间最优解;``diagonal`` 保存更新前的内层值,``dp[right-1]`` 保存当前左端下的左侧区间。时间复杂度为 ``O(n^2)``,空间复杂度压缩为 ``O(n)``。