給定一個字串
s，找出其中最長回文子序列的長度。
Example:
Input: s = “bbbab” Output: 4 (子序列 “bbbb”)
Intuition
TIP
區間 DP：若兩端字元相同就收縮，否則取去掉左端或右端的較大值。
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]) - 等價於求
s和s.reversed()的 LCS
Approaches
1. Interval DP — O(n^2) / O(n^2)
- Idea: 從短區間到長區間填表，
dp[i][j]為s[i..j]的最長回文子序列長度。 - Time:
O(n^2) - Space:
O(n^2)
class Solution {
fun longestPalindromeSubseq(s: String): Int {
val n = s.length
val dp = Array(n) { IntArray(n) }
for (i in n - 1 downTo 0) {
dp[i][i] = 1
for (j in i + 1 until n) {
dp[i][j] = if (s[i] == s[j]) {
dp[i + 1][j - 1] + 2
} else {
maxOf(dp[i + 1][j], dp[i][j - 1])
}
}
}
return dp[0][n - 1]
}
}⭐ 2. 1D DP (Space Optimized) — O(n^2) / O(n)
- Idea: 由於
dp[i][j]只依賴dp[i+1][j-1]、dp[i+1][j]、dp[i][j-1]，可以壓縮為一維陣列加一個暫存變數。 - Time:
O(n^2) - Space:
O(n)
class Solution {
fun longestPalindromeSubseq(s: String): Int {
val n = s.length
val dp = IntArray(n)
for (i in n - 1 downTo 0) {
dp[i] = 1
var prev = 0 // dp[i+1][j-1]
for (j in i + 1 until n) {
val temp = dp[j]
dp[j] = if (s[i] == s[j]) {
prev + 2
} else {
maxOf(dp[j], dp[j - 1])
}
prev = temp
}
}
return dp[n - 1]
}
}🔑 Takeaways
- Pattern: 區間 DP —
dp[i][j]依賴子區間，從短到長填表 - Key trick: 最長回文子序列等價於原字串與反轉字串的 LCS；區間 DP 可壓縮空間至 O(n)