LeetCode 115 Distinct Subsequences - Example and Complexity Analysis

Trace s = "abb", t = "ab".

Initialize: dp[i][0] = 1 for all i (empty string matches once).

i=1 (s[0]='a'), j=1 (t[0]='a'): Match! dp[1][1] = dp[0][0] + dp[0][1] = 1 + 0 = 1.

i=1, j=2: s[0]='a' ≠ t[1]='b'. dp[1][2] = dp[0][2] = 0.

i=2 (s[1]='b'), j=1: No match. dp[2][1] = dp[1][1] = 1.

i=2, j=2: s[1]='b' == t[1]='b'. Match! dp[2][2] = dp[1][1] + dp[1][2] = 1 + 0 = 1.

i=3 (s[2]='b'), j=2: Match! dp[3][2] = dp[2][1] + dp[2][2] = 1 + 1 = 2.

Answer: $2$ (use first 'b' or second 'b').

$O(m \times n)$ time and space.