LeetCode 516 Longest Palindromic Subsequence - State Design

$dp[i][j]$ = the length of the longest palindromic subsequence in $s[i..j]$. Why this formulation? Palindromes have a natural interval structure. They're defined by their endpoints. When you add characters at both ends, you need to know the answer for the inner substring.

Base cases: $dp[i][i] = 1$ (a single character is a palindrome of length $1$). $dp[i][i-1] = 0$ (empty range, used when $i > j$ in the recurrence). The final answer is $dp[0][n-1]$, covering the entire string. Fill the table by increasing interval length, so smaller intervals are ready when you need them.