DP Longest Palindromic Subsequence¶
Table of Contents¶
- 516. Longest Palindromic Subsequence (Medium)
- 730. Count Different Palindromic Subsequences (Hard)
- 1312. Minimum Insertion Steps to Make a String Palindrome (Hard)
- 1771. Maximize Palindrome Length From Subsequences (Hard)
- 1682. Longest Palindromic Subsequence II (Medium) 👑
- 1216. Valid Palindrome III (Hard) 👑
- 1246. Palindrome Removal (Hard) 👑
516. Longest Palindromic Subsequence¶
"""
- Return the length of the longest palindromic subsequence in `s`.
- Bottom-up DP table
| dp | b | b | b | a | b |
| :-: | :-: | :-: | :-: | :--------------: | :----------: |
| b | 1 | 2 | 3 | 3 | 4 |
| b | 0 | 1 | 2 | 2 | 3 `dp[i][j]` |
| b | 0 | 0 | 1 | 1 `dp[i+1][j-1]` | 2 |
| a | 0 | 0 | 0 | 1 | 1 |
| b | 0 | 0 | 0 | 0 | 1 |
"""
def longestPalindromeSubseq(s: str) -> int:
n = len(s)
dp = [[0] * n for _ in range(n)]
for i in range(n):
dp[i][i] = 1
for i in range(n - 1, -1, -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][j - 1], dp[i + 1][j])
return dp[0][-1]
print(longestPalindromeSubseq("bbbab")) # 4