527. Count Common Subsequence Pairs

Count the pairs (I, J) where I is a set of positions in the first string, J is a set of positions in the second, and the two spell the SAME string. The empty pair counts.

Print the count modulo 1000000007.

ab, ab -> 4 empty, a with a, b with b, ab with ab a, b -> 1 only the empty pair aa, a -> 3 empty, first a with a, second a with a

## The inclusion and exclusion

dp[i][j] = the number of pairs using only the first i and first j characters

Every pair either omits position i of the first string, omits position j of the second, or uses both. Adding dp[i-1][j] and dp[i][j-1] counts the first two families and double counts the pairs omitting BOTH:

a[i-1] != b[j-1] -> dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]

When the characters MATCH there is an extra family: any pair from dp[i-1][j-1] extended by matching these two positions against each other. That adds dp[i-1][j-1], which cancels the subtraction:

a[i-1] == b[j-1] -> dp[i][j] = dp[i-1][j] + dp[i][j-1]

## Why the cancellation is worth understanding

The matching case has two terms and the non-matching case has three, which is the reverse of the shape people expect from problem #237 where matching is the SIMPLER branch with a plus one.

The reason is the same as in problem 521: the subtraction and the new family are the same quantity, so they cancel exactly. Both problems are inclusion and exclusion over an interval or a grid, and in both the cancellation is what makes one branch look too short.

Being able to rederive that, rather than remembering which branch has which count of terms, is the difference between the two problems being one idea and being two formulas.

## The base row and column

dp[0][j] = 1 and dp[i][0] = 1, for every i and j: the only pair available when one side has no characters is the empty pair.

Setting them to 0 makes every entry 0. Setting only dp[0][0] = 1 and leaving the rest of the row and column at 0 undercounts, and the error is subtle: the answer comes out too small by a varying amount rather than uniformly, which is harder to spot than a constant offset.

## Negatives under the modulus

The non-matching branch subtracts, so add the modulus before reducing in every language except Python. The same asymmetry as problem 521.

## Counting by position

aa against a answers 3, not 2, because the two as of the first string are different POSITIONS and each pairs with the single a of the second. Counting distinct STRINGS would give 2.

aa against aa answers 6 and aab against aba answers 9, both of which need the positional reading.

## Cost

Time O(n m). Space O(m) with two rows.

Constraints - `1 ≤ length of a ≤ 2000` - `1 ≤ length of b ≤ 2000` - both contain only lowercase letters