521. 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).

Constraints - `1 ≤ length of s ≤ 2000` - `s` contains only lowercase letters