Pattern visualizer
Distinct Subsequences
Build a table where dp[i][j] answers: how many ways does the first j characters of s spell out the first i characters of t? Every character of s has exactly one choice to make: get skipped, or get used. Skipping always carries forward whatever dp[i][j-1] already counted. Using it only makes sense when s[j-1] equals the next character t needs, t[i-1] — and when it does, every way of matching t[0..i-2] out of s[0..j-2] becomes a new way of matching t[0..i-1] out of s[0..j-1]. The two contributions never overlap, so they add. Animated on: s = "baba", t = "ba" — count the distinct ways to delete characters from s so what remains equals t..
dp[i][j] = dp[i][j-1] (skip s[j-1]) + dp[i-1][j-1] when s[j-1] closes a match on t[i-1]
dp over t="ba" (rows) x s="baba" (cols) — dp[i][j] = ways s[0..j-1] forms t[0..i-1]
dp[0][j] = 1 for every j: the empty target "" is formed exactly one way from any prefix of s — by deleting everything.
1FUNCTION numDistinct(s, t):2 m <- LENGTH(s)3 n <- LENGTH(t)4 FOR j FROM 0 TO m: dp[0][j] <- 15 FOR i FROM 1 TO n:6 FOR j FROM 1 TO m:7 dp[i][j] <- dp[i][j-1]8 IF s[j-1] = t[i-1]:9 dp[i][j] <- dp[i][j] + dp[i-1][j-1]10 RETURN dp[n][m]
← / → step · space play · Home restart