代码1

dp
An example:
S: [acdabefbc]
T: [ab]

first we check with a:

           *  *
      S = [acdabefbc] 
mem[1] = [0111222222]

then we check with ab:

              *  * 
      S = [acdabefbc]
mem[1] = [0111222222]
mem[2] = [0000022244]

Runtime: 14 ms, faster than 19.61% of Java online submissions for Distinct Subsequences.

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