Distinct Subsequences — Step-by-Step Visualization

Algorithm Pattern

2D Dynamic Programming

Key Idea

We use a 2D DP table `dp[i][j]` to represent the number of subsequences of `s[:i]` that match `t[:j]`. If `s[i-1] == t[j-1]`, we have two choices: (1) use `s[i-1]` to match `t[j-1]`, adding `dp[i-1][j-1]` ways, or (2) skip `s[i-1]` and match `t[j-1]` using `s[:i-1]`, adding `dp[i-1][j]` ways. If they don't match, we must skip `s[i-1]`.

Step-by-Step Approach

1. Initialize `dp` table of size `(m+1) x (n+1)` with 0.
2. Base Case: `dp[i][0] = 1` for all `i` (an empty target `t` can always be matched by skipping everything in `s`).
3. Iterate through the table: If `s[i-1] == t[j-1]`, `dp[i][j] = dp[i-1][j-1] + dp[i-1][j]`.
4. Otherwise, `dp[i][j] = dp[i-1][j]`.

Common Gotchas

• The order of strings on axes matters for intuition. Usually `s` is the row (source) and `t` is the column (target).
• The base case `dp[i][0] = 1` is crucial; it says there's 1 way to match an empty string from any prefix of `s`.