Implement the solution to the Distinct Subsequences problem using dynamic programming.?

The Distinct Subsequences problem is as follows: given two strings ‘s‘ and ‘t‘, count the number of distinct subsequences of ‘t‘ in ‘s‘.

We can solve this problem using dynamic programming. Let ‘dp[i][j]‘ be the number of distinct subsequences of ‘t‘ in ‘s‘ up to index ‘i‘ of ‘s‘ and up to index ‘j‘ of ‘t‘. If ‘s[i] == t[j]‘, then we can either include or exclude ‘s[i]‘ in the subsequence. If we include ‘s[i]‘, then the number of distinct subsequences is ‘dp[i-1][j-1]‘. If we exclude ‘s[i]‘, then the number of distinct subsequences is ‘dp[i-1][j]‘. If ‘s[i] != t[j]‘, then we can only exclude ‘s[i]‘ and the number of distinct subsequences is ‘dp[i-1][j]‘.

The base cases are ‘dp[0][0] = 1‘ and ‘dp[i][0] = 1‘ for all ‘i‘, since there is only one way to form the empty subsequence. Also, ‘dp[0][j] = 0‘ for all ‘j > 0‘, since there are no subsequences of ‘t‘ in an empty string.

The final answer is ‘dp[m][n]‘, where ‘m‘ and ‘n‘ are the lengths of ‘s‘ and ‘t‘, respectively.

Here is the Java code to implement the above approach:

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

Let’s go over an example to see how this works. Consider ‘s = "babgbag"` and ‘t = "bag"`. The dp table would look like:

    b  a  g
  0 1  0  0
b 1 1  0  0
a 1 1  1  0
b 2 1  1  0
g 3 1  1  1
b 3 4  1  1
a 3 4  5  1
g 3 4  5  6

The final answer is ‘dp[7][3] = 6‘, which is the number of distinct subsequences of ‘t = "bag"` in ‘s = "babgbag"`.