115 distinct subsequences

https://leetcode.com/problems/distinct-subsequences/

其实，这可以看作是一个01背包问题，t看作背包，s中的字母是物品，满足条件的字母可以放进背包

dp[i][j]是s的前i个字母中填满amout为j的背包的放法，即s的前i个字母中sub seq为t的前j个字母的数量

class Solution {
    public int numDistinct(String s, String t) {
        char[] sarr = s.toCharArray();
        char[] tarr = t.toCharArray();
        int m = sarr.length;
        int n = tarr.length;
        // dp[i][j] number of ways that sub seqs in s of lenth i equals to t of len j
        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++) {
                if (sarr[i-1] != tarr[j-1]) {
                    dp[i][j] = dp[i-1][j];
                } else {
                // 这里必须是dp[i-1][j-1]而非dp[i][j-1]。不然你会有一堆重复的
                    dp[i][j] = dp[i-1][j] + dp[i-1][j-1];
                }
            }
        }
        return dp[m][n];
    }
}