LeetCode 516 Longest Palindromic Subsequence - Walkthrough

Trace LPS on $s = \text{"bbbab"}$. Build $dp[i][j]$ = LPS length for $s[i..j]$. Base cases: $dp[i][i] = 1$ (single char).

Iterate by length. Length $2$: $dp[0][1] = 2$ ("bb"), $dp[1][2] = 2$ ("bb"), $dp[2][3] = 1$ ("ba"), $dp[3][4] = 1$ ("ab"). Length $3$, $4$, $5$: keep expanding. Final $dp[0][4] = 4$. The LPS is "bbbb". The observation: when endpoints match, they contribute $2$ to the palindrome length plus the inner solution.