1def longest_palindromic_subsequence(s):
2 if not s:
3 return 0
4 n = len(s)
5 dp = [[0] * n for _ in range(n)]
6 for i in range(n - 1, -1, -1):
7 dp[i][i] = 1
8 for j in range(i + 1, n):
9 if s[i] == s[j]:
10 dp[i][j] = dp[i + 1][j - 1] + 2
11 else:
12 dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
13 return dp[0][n - 1]