Distinct Palindromic Subsequences — Solution & Editorial

Back to the Problem

Interval DP: when the endpoints match, dp[i][j] = 2·dp[i+1][j−1] + 2 (the +2 for the two-character and single-character palindromes of that pair); otherwise inclusion–exclusion over dropping an end.

Complexity: O(|S|²)

Watch out: The matching-ends case double-counts inner palindromes plus the new pair; the subtraction case removes the overlap dp[i+1][j−1].