424. 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.

Constraints - `1 ≤ length of s ≤ 1000` - `1 ≤ length of t ≤ 1000` - Both are lowercase English letters. - The answer fits in a signed 64-bit integer.