Distinct Subsequences

Given two sequences A, B, count number of unique ways in sequence A, to form a subsequence that is identical to the sequence B.

Subsequence : A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, “ACE” is a subsequence of “ABCDE” while “AEC” is not).

The first argument of input contains a string, A.
The second argument of input contains a string, B.

Return an integer representing the answer as described in the problem statement.

1 <= length(A), length(B) <= 700

Input 1:
    A = "abc"
    B = "abc"
    
Output 1:
    1

Explanation 1:
    Both the strings are equal.

Input 2:
    A = "rabbbit" 
    B = "rabbit"

Output 2:
    3

Explanation 2:
    These are the possible removals of characters:
        => A = "ra_bbit" 
        => A = "rab_bit" 
        => A = "rabb_it"
        
    Note: "_" marks the removed character.

Method:

（一）状态

f[i][j]表示s1的前i个字符的子序列中，包含多少个s2的前 j 个字符子串
（二）转移方程

如果s1的第 i 个字符和s2的第 j 个字符不同的话，
意味着s1的第 i 个字符，必不参与组成子序列

f[i][j] = f[i - 1][j]
（例如 abc, ab) f[3][2] = f[2][2]
如果s1的第 i 个字符和s2的第 j 个字符相同的话，
意味着s1的第 i 个字符，可以参与组成子序列，也可不参与组成子序列

f[i][j] = f[i - 1][j - 1] + f[i - 1][j]
(例如 abcc, abc) f[4][3] = f[3][2] + f[3][3]
（三）初始化

s1的前 i 个字符和s2的前 0 个字符，意味着 s1 中子序列等于空串的个数都是 1
f[i][0] = 1
（四）结果

f[m][n]

Solution:

Time: O(mn)
Space: O(mn)

public class Solution {
    public int numDistinct(String A, String B) {
        int m = B.length();
        int n = A.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i ++) {
            // if A is empty, it's not possibie to get B
            dp[i][0] = 0;
        }
        for (int j = 0; j <= n; j ++) {
            // if B is empty, we need to remove all chars in A, and there is one way
            dp[0][j] = 1;
        }
        for (int i = 1; i <= m; i ++) {
            for (int j = 1; j <= n; j ++) {
                // we don't pick this char from A
                dp[i][j] = dp[i][j - 1];
                if (A.charAt(j - 1) == B.charAt(i - 1)) {
                    // we can pick this char from A
                    dp[i][j] += dp[i - 1][j - 1];
                }
            }
        }
        return dp[m][n];
    }
}

Space optimized:

public class Solution {
    public int numDistinct(String A, String B) {
        int m = B.length();
        int n = A.length();
        int[] dp = new int[n + 1];
        // dp[0][j] = 1
        int pre = 1;
        for (int i = 0; i <= m; i ++) {
            for (int j = 0; j <= n; j ++) {
                int temp = dp[j];
                // we don't pick this char from A
                if (i == 0) {
                    // first row
                    dp[j] = 1;
                } else if (j == 0) {
                    // first column
                    dp[j] = 0;
                } else {
                    // always add dp[i][j - 1]
                    dp[j] = dp[j - 1];
                    if (A.charAt(j - 1) == B.charAt(i - 1)) {
                        // we can pick this char from A
                        dp[j] += pre;
                    }
                }
                pre = temp;
            }
        }
        return dp[n];
    }
}