无法播放？请 点击这里 跳转到Youtube
切换视频源：

题目链接: https://leetcode.com/problems/distinct-subsequences

GitHub答案源代码请点击这里

DFS + Memo：

class Solution {
    Integer[][] memo;
    public int numDistinct(String s, String t) {
        memo = new Integer[s.length() + 1][t.length() + 1];
        return dfs(s, t, s.length(), t.length());
    }
    
    private int dfs(String s, String t, int i, int j) {
        if (j == 0) {
            return 1;
        }
        if (i == 0) {
            return 0;
        }
        
        if (memo[i][j] != null) {
            return memo[i][j];
        }
        
        int res = 0;
        if (s.charAt(i - 1) == t.charAt(j - 1)) {
            res = dfs(s, t, i - 1, j - 1) + dfs(s, t, i - 1, j);
        } else {
            res = dfs(s, t, i - 1, j);
        }
        
        memo[i][j] = res;
        return res;
    }
}

正向DP 

class Solution {
    public int numDistinct(String s, String t) {
        int[][] dp = new int[s.length() + 1][t.length() + 1];
        for (int i = 0; i < dp.length; i++)
            dp[i][0] = 1;
        
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 1; j <= t.length(); 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[s.length()][t.length()];
    }
}