Longest Palindromic Subsequence — filling the interval table

Recurrencedp[i][j] = s[i]==s[j] ? dp[i+1][j-1] + 2 : max(dp[i+1][j], dp[i][j-1]) dp[i][j] = longest palindromic subsequence inside the interval i..j. Matching endpoints wrap the inner interval (+2); otherwise drop one end and take the better. Each cell needs the row below and column to the left, so rows fill bottom-up, left to right. Base: the diagonal is 1.

String:

dp — rows: start i · columns: end j (upper triangle)

diagonal (single chars) current interval inner interval (match) drop an end (no match)