LeetCode 516: Longest Palindromic Subsequence (Interval DP on String)
LeetCode 516Dynamic ProgrammingStringInterval DPToday we solve LeetCode 516 - Longest Palindromic Subsequence.
Source: https://leetcode.com/problems/longest-palindromic-subsequence/
English
Problem Summary
Given a string s, return the length of the longest subsequence of s that is also a palindrome.
Key Insight
Use interval DP: let dp[i][j] be the longest palindromic subsequence length within substring s[i..j]. We build answers from short intervals to long intervals.
Recurrence
If s[i] == s[j], then these two characters can wrap an inner palindrome: dp[i][j] = dp[i+1][j-1] + 2.
Otherwise, we must skip one side: dp[i][j] = max(dp[i+1][j], dp[i][j-1]).
Base case: dp[i][i] = 1.
Optimal Algorithm Steps
1) Let n = s.length(), create n x n DP table.
2) Set all diagonal cells to 1.
3) Iterate i from n-1 down to 0.
4) For each i, iterate j from i+1 to n-1, apply recurrence.
5) Answer is dp[0][n-1].
Complexity Analysis
Time: O(n^2).
Space: O(n^2).
Common Pitfalls
- Wrong traversal order (must guarantee subproblems are ready).
- Forgetting base case dp[i][i] = 1.
- Using substring DP for subsequence problem (different recurrence).
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int longestPalindromeSubseq(String s) {
int n = s.length();
int[][] dp = new int[n][n];
for (int i = n - 1; i >= 0; i--) {
dp[i][i] = 1;
for (int j = i + 1; j < n; j++) {
if (s.charAt(i) == s.charAt(j)) {
dp[i][j] = dp[i + 1][j - 1] + 2;
} else {
dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
}
}
}
return dp[0][n - 1];
}
}func longestPalindromeSubseq(s string) int {
n := len(s)
dp := make([][]int, n)
for i := range dp {
dp[i] = make([]int, n)
}
for i := n - 1; i >= 0; i-- {
dp[i][i] = 1
for j := i + 1; j < n; j++ {
if s[i] == s[j] {
dp[i][j] = dp[i+1][j-1] + 2
} else {
if dp[i+1][j] > dp[i][j-1] {
dp[i][j] = dp[i+1][j]
} else {
dp[i][j] = dp[i][j-1]
}
}
}
}
return dp[0][n-1]
}class Solution {
public:
int longestPalindromeSubseq(string s) {
int n = (int)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 + 1][j], dp[i][j - 1]);
}
}
}
return dp[0][n - 1];
}
};class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
n = len(s)
dp = [[0] * n for _ in range(n)]
for i in range(n - 1, -1, -1):
dp[i][i] = 1
for j in range(i + 1, n):
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][n - 1]var longestPalindromeSubseq = function(s) {
const n = s.length;
const dp = Array.from({ length: n }, () => Array(n).fill(0));
for (let i = n - 1; i >= 0; i--) {
dp[i][i] = 1;
for (let j = i + 1; j < n; j++) {
if (s[i] === s[j]) {
dp[i][j] = dp[i + 1][j - 1] + 2;
} else {
dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
}
}
}
return dp[0][n - 1];
};中文
题目概述
给定字符串 s，返回其中最长回文子序列的长度。
核心思路
使用区间动态规划。定义 dp[i][j] 为子串 s[i..j] 内最长回文子序列长度。按区间长度从短到长递推。
状态转移
若 s[i] == s[j]，两端字符可包住内部回文：dp[i][j] = dp[i+1][j-1] + 2。
否则只能舍弃一端：dp[i][j] = max(dp[i+1][j], dp[i][j-1])。
基础状态：dp[i][i] = 1。
最优算法步骤
1）设 n = s.length()，创建 n x n 的 DP 表。
2）对角线全部设为 1。
3）外层 i 从 n-1 递减到 0。
4）内层 j 从 i+1 增加到 n-1，按转移公式更新。
5）最终答案为 dp[0][n-1]。
复杂度分析
时间复杂度：O(n^2)。
空间复杂度：O(n^2)。
常见陷阱
- 遍历顺序错误，导致子问题尚未计算。
- 忘记初始化 dp[i][i] = 1。
- 把“子序列”误当“子串”处理，状态转移会错。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int longestPalindromeSubseq(String s) {
int n = s.length();
int[][] dp = new int[n][n];
for (int i = n - 1; i >= 0; i--) {
dp[i][i] = 1;
for (int j = i + 1; j < n; j++) {
if (s.charAt(i) == s.charAt(j)) {
dp[i][j] = dp[i + 1][j - 1] + 2;
} else {
dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
}
}
}
return dp[0][n - 1];
}
}func longestPalindromeSubseq(s string) int {
n := len(s)
dp := make([][]int, n)
for i := range dp {
dp[i] = make([]int, n)
}
for i := n - 1; i >= 0; i-- {
dp[i][i] = 1
for j := i + 1; j < n; j++ {
if s[i] == s[j] {
dp[i][j] = dp[i+1][j-1] + 2
} else {
if dp[i+1][j] > dp[i][j-1] {
dp[i][j] = dp[i+1][j]
} else {
dp[i][j] = dp[i][j-1]
}
}
}
}
return dp[0][n-1]
}class Solution {
public:
int longestPalindromeSubseq(string s) {
int n = (int)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 + 1][j], dp[i][j - 1]);
}
}
}
return dp[0][n - 1];
}
};class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
n = len(s)
dp = [[0] * n for _ in range(n)]
for i in range(n - 1, -1, -1):
dp[i][i] = 1
for j in range(i + 1, n):
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][n - 1]var longestPalindromeSubseq = function(s) {
const n = s.length;
const dp = Array.from({ length: n }, () => Array(n).fill(0));
for (let i = n - 1; i >= 0; i--) {
dp[i][i] = 1;
for (let j = i + 1; j < n; j++) {
if (s[i] === s[j]) {
dp[i][j] = dp[i + 1][j - 1] + 2;
} else {
dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
}
}
}
return dp[0][n - 1];
};
Comments