📜 WAYPOINT LESSON
Palindromic Intervals
⭐⭐⭐ advanced⏳ 30 min read📍 Lesson 163 of 281
The longest palindromic subsequence matches the outer chars or drops one side — an O(n^2) interval DP with no split loop.
Palindromes as intervals
If s[i] == s[j], dp[i][j] = dp[i+1][j-1] + 2; otherwise drop one end. No split loop at all — the recurrence branches on equality instead of enumerating k. This is the lightest interval DP, and the one whose greedy impostors fail fastest.
⚡ Now practice
Ready to CodeInterval TrioMatrix-chain multiplication, linear stone merging, and longest palindromic subsequence under a 50-case load.
3 challenges · · ~110 min