How Many Ways to Spell It
Count how many distinct subsequences of s equal t. Two subsequences are
distinct when they use different POSITIONS, even if the characters are identical.
s = rabbbit, t = rabbit -> 3 the three ways to choose two of the three b's
s = babgbag, t = bag -> 5
The count is guaranteed to fit in a signed 64-bit integer.
This is the counting cousin of the longest common subsequence, and the difference is one operator. LCS takes a MAXIMUM over its branches; counting must ADD them, because the branches describe disjoint sets of solutions rather than competing options.
ways(i, j) = number of ways to spell t[j..] using s[i..]
ways(i, j) = ways(i+1, j) skip s[i]
+ ways(i+1, j+1) if s[i] == t[j] use s[i] for t[j]
Both branches are taken when the characters match, and that is the whole problem: skipping a usable character is a genuinely different set of subsequences, not a worse one.
The base cases decide correctness. Running out of t is ONE way, the empty
match, so it returns 1. Running out of s with t unfinished is 0 ways.
Returning 0 for the first is the most common error and makes every answer 0.
Bottom-up, the first column is all 1s, for the same reason.