103. Distinct Subsequences

dp[i][j] counts how many subsequences of the first i chars of s equal the first j chars of t. You can always skip s[i-1]; if it matches t[j-1] you may also use it.

Definition

dp[i][j] = number of distinct subsequences of s[:i] equal to t[:j].

Transition

You always have the option to not use s[i-1]: dp[i][j] = dp[i-1][j]. If s[i-1] == t[j-1], you may additionally use it, pairing it with t[j-1]: add dp[i-1][j-1].

dp[i][j] = dp[i-1][j] + (dp[i-1][j-1] if s[i-1]==t[j-1] else 0)

Base: dp[i][0] = 1 (the empty target is matched exactly once — by deleting everything).

Worked example

s = "rabbbit", t = "rabbit": the three b's give 3 ways to line up 'rabbit'.

Complexity

• Time: O(m·n).
• Space: O(m·n) (reducible to O(n)).

class Solution {
    public int numDistinct(String s, String t) {
        int m = s.length(), n = t.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) dp[i][0] = 1;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = dp[i - 1][j];
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[i][j] += dp[i - 1][j - 1];
                }
            }
        }
        return dp[m][n];
    }
}