Leetcode--Java--115. 不同的子序列

给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。

字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，“ACE” 是 “ABCDE” 的一个子序列，而 “AEC” 不是）

题目数据保证答案符合 32 位带符号整数范围。

示例 1：

输入：s = "rabbbit", t = "rabbit"
输出：3
解释：
如下图所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
rabbbit
rabbbit
rabbbit

动态规划

1. 状态表示和计算如下：
   

class Solution {
    public int numDistinct(String s, String t) {
          int m = s.length(), n = t.length();
          //可能会在过程中溢出，所以用long来存
          //f[i][j]表示s中1~i与t中1~j子序列相同的个数
          long f[][] = new long[m + 1][n + 1];
          s = ' ' + s;
          t = ' ' + t;
          //初始化边界，如果t中为0，就是不需要选，就能和t中相等
          for (int i = 0; i <= m; i ++ ) {
              f[i][0] = 1;
          }
          for (int i = 1; i <= m; i ++ ) {
              for (int j = 1; j <= n; j ++ ) {
                  //先统计不选的方案
                  f[i][j] = f[i - 1][j];
                  //统计选的，前提是要等于t[j]
                  if (s.charAt(i) == t.charAt(j)) {
                      //注意是加等，因为方案数要累计求和
                      f[i][j] += f[i - 1][j - 1];
                  }
              }
          }
          return (int)f[m][n];
    }
}