- DP question
dp[i][j]means the longest palindrome in
- To compare
s[j], there are 2 situations:
s[i] !== s[j], we have to separately consider putting either
dp[i][j] = Math.max(dp[i][j-1], dp[i+1][j]).
s[i] === s[j], there are also two situations:
i === j, it’s the same char! Then
dp[i][j] = 1.
i !== j, 2 different chars, then
dp[i][j] = dp[i+1][j-1] + 2.
Given a string s, find the longest palindromic subsequence’s length in s.
A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.
Input: s = "bbbab"