Solution0115.java

// 115. 不同的子序列


/*
动态规划：
1、题目简化：求s的子序列中t出现的个数
1、定义dp数组：dp[i][j] 表示 s前i个字符 中出现 t前j个字符 的个数
2、初始化：
  1）二维dp数组扩容：增加空字符串这一最小规模的情况，方便直观初始化
  2）dp[i][0] = 1 表示 s前i个字符 中出现 t前0个字符 的个数为1，即空字符串是任何字符串的子集
     dp[0][j] = 0 表示 s前0个字符 中出现 t前j个字符 的个数为0，即空字符串不会出现任何字符串
     dp[0][0] = 1 表示 s前i个字符 中出现 t前0个字符 的个数为1，即空字符串是空字符串的子集
3、状态转移方程：
  1）s中不同索引位置的字符组合，代表不同的子序列
  2）如果s[i] == s[j]，那么s有两种方式可以匹配t
    第一种是用s[i]匹配掉t[j]，那么出现个数为 s前i-1个字符中出现t前j-1个字符的个数，即 dp[i - 1][j - 1]
    第二种是不用s[i]匹配t[j]，那么出现个数为 s前i-1个字符中出现t前j个字符的个数，即 dp[i - 1][j]
    所以 dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
  3）如果s[i] != s[j]，那么s只能不用s[i]匹配t[j]，那么出现个数为 s前i-1个字符中出现t前j个字符的个数，即 dp[i - 1][j]
    所以 dp[i][j] = dp[i - 1][j];
4、遍历dp数组填表：
  1）两个for循环遍历二维dp数组每个位置，根据状态转移方程计算该位置的出现个数
  2）遍历顺序决定了哪些位置是计算过的、是已知状态，外层遍历字符串s，内层遍历字符串t。
    从二维数组角度看，遍历顺序是从上到下，从左到右，所以遍历到(i,j)位置时，其左方、上方、左上方状态都已经遍历计算过了。
    从两个字符串角度看，两个指针分别指向两个字符串，两者遍历顺序都是从左到右，所以遍历到(i,j)位置时，其左边其他位置都遍历计算过了。
    所以求 dp[i][j] 时，dp[i - 1][j - 1]、dp[i - 1][j] 都是已知状态了
5、返回结果：最后一个状态就是结果

s = "babgbag", t = "bag"
二维数组：
  ''  b  a  g
'' 1  0  0  0
b  1  1  0  0
a  1  1  1  0
b  1  2  1  0
g  1  3  1  1
b  1  3  4  1
a  1  3  4  1
g  1  3  4  5

字符串：
s:  b  a  b  g  b  a  g
                      ↑
                      i
t:  b  a  g
          ↑
          j
 */
class Solution {
    public int numDistinct(String s, String t) {
        int n = s.length(), m = t.length();
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 1;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; 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[n][m];
    }
}