Hints — p74 Distinct Subsequences

Hint 1. This is a counting DP — not boolean, not min/max. Define dp[i][j] = number of distinct subsequences of s[:i] equal to t[:j]. Combiner will be +, not OR / max / min.

Hint 2. Recurrence — case on whether s[i-1] == t[j-1]:

• If they differ: must skip s[i-1] → dp[i][j] = dp[i-1][j].
• If they match: two disjoint choices — use s[i-1] to match t[j-1] (dp[i-1][j-1]) OR skip it (dp[i-1][j]). Sum: dp[i][j] = dp[i-1][j-1] + dp[i-1][j].

Hint 3. Base cases matter: dp[i][0] = 1 for all i (empty t has exactly one matching subsequence — the empty one). dp[0][j] = 0 for j ≥ 1.

Hint 4. “Distinct” doesn’t mean distinct-as-strings — it means each subsequence (an index set into s) is counted once. The DP naturally counts index sets; s="aa", t="a" → 2.

Hint 5. Space optimization: reduce to 1D array of length n+1. Iterate j from RIGHT TO LEFT so dp[j-1] still refers to the previous row.

If stuck: see solution.py.