Count the Palindromic Subsequences
Count the non-empty palindromic SUBSEQUENCES, identified by which POSITIONS they use. Two selections using different positions count separately even if they spell the same string.
Print the count modulo 1000000007.
aab -> 4 a, a, b, aa
aa -> 3 a, a, aa
aba -> 5 a, b, a, aa, aba
## The interval recurrence, and the double count
dp[i][j] = the number of palindromic subsequences within s[i..j]
Every such subsequence either avoids s[i], avoids s[j], or uses both. Adding
dp[i+1][j] and dp[i][j-1] counts those avoiding s[i] and those avoiding s[j], and
the ones avoiding BOTH have been counted twice:
s[i] != s[j] -> dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]
The subtraction is inclusion and exclusion, and forgetting it inflates the answer.
## The matching case, and why the subtraction disappears
When s[i] == s[j], there is an extra family: take any palindromic subsequence strictly
inside and wrap it in the two equal characters, plus the pair s[i] s[j] on its own. That
is dp[i+1][j-1] + 1 new subsequences.
dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1] + dp[i+1][j-1] + 1
= dp[i+1][j] + dp[i][j-1] + 1
The two dp[i+1][j-1] terms cancel exactly. That cancellation is the reason the matching
case looks suspiciously simple, and knowing WHY it is simple is the difference between
remembering the formula and being able to rederive it.
## Negative intermediates under a modulus
The non-matching case SUBTRACTS. Under a modulus the result can be negative, so write it as
(dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1] + MOD) % MOD
In Python the % operator already returns a non-negative value, so the bug is invisible
there and appears only in C, C++, Java and JavaScript. That asymmetry is worth knowing: a
solution developed in Python and ported can fail for a reason the original never showed.
## The fill order and the empty interval
Fill by increasing LENGTH, since every dependency is a shorter interval.
At length == 2, dp[i+1][j-1] is the empty interval and must contribute 0. With
s[i] == s[j] that gives 1 + 1 + 1 = 3 for aa, which is correct: a, a, aa.
## Counting by position
aaa answers 7: three singles, three pairs, one triple. Not 3, which is what counting
DISTINCT strings would give, since a and aa and aaa are the only distinct
palindromes.
Counting distinct strings is a genuinely harder problem. The statement declares the convention, because both readings are sensible and the answers differ a lot.
## Cost
Time O(n^2). Space O(n^2).