LeetCode 115 Distinct Subsequences - Solution

The core idea

Define dp[i][j] = number of ways to form first j characters of t using first i characters of s.

If s[i-1] == t[j-1]: we can either use this character or skip it. dp[i][j] = dp[i-1][j-1] + dp[i-1][j].

If characters don't match: we must skip s[i-1]. dp[i][j] = dp[i-1][j].

Base: dp[i][0] = 1 (empty t matches any prefix of s one way). Answer: dp[m][n].