题目描述

image.png

解题思路

🔗
这道题目如果不是子序列，而是要求连续序列的，那就可以考虑用KMP。

  • 确定dp数组（dp table）以及下标的含义

dp[i][j]：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。

  • 确定递推公式

这一类问题，基本是要分析两种情况

  • s[i - 1] 与 t[j - 1]相等：相等就是用本身来匹配，也就是dp[i - 1][j - 1]，但也可以使用dp[i-1][j]来匹配，例如:bagg 和 bag 的匹配当两个字符串的最后一个g相等时，可以使用倒数第二个g和a匹配，也可以是倒数第二个g和g匹配。（注意这里为什么dp[i-1][j-1]不加1，因为这里的dp含义是个数，而不是上一题dp含义是长度）
  • s[i - 1] 与 t[j - 1] 不相等：不相等即为上一次匹配的dp[i - 1][j]
    • dp数组如何初始化

t为0时，s可以全部删除，所以有一个子序列，而s为空，那么无论怎么删除都不会为t。
所以dp[i][0]初始化为1，dp[0][j]初始化为0；

  • 确定遍历顺序

从递推公式dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]; 和 dp[i][j] = dp[i - 1][j]; 中可以看出dp[i][j]都是根据左上方和正上方推出来的。
所以遍历的时候一定是从上到下，从左到右，这样保证dp[i][j]可以根据之前计算出来的数值进行计算。

  • 举例推导dp数组

以s：”baegg”，t：”bag”为例，推导dp数组状态如下：
image.png

  1. public int numDistinct(String s, String t) {
  2.     // dp[i][j]：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。
  3.     int[][] dp = new int[s.length() + 1][t.length() + 1];
  4.     // 初始化左上两边
  5.     dp[0][0] = 1;   // s为0，t为0，那么空字符串s删除元素之后编程空字符串t（特殊情况）
  6.     for (int i = 1; i < s.length() + 1; i++) {
  7.         dp[i][0] = 1;   // s中删除元素，删除到空字符时和空字符t匹配，所以有一种
  8.     }
  10.     for (int i = 1; i < t.length(); i++) {
  11.         dp[0][i] = 0;   // s为空，那么怎么删除都不可能会和t项匹配
  12.     }
  14.     //            这一类问题，基本是要分析两种情况
  15.     //            s[i - 1] 与 t[j - 1]相等
  16.     //            s[i - 1] 与 t[j - 1] 不相等
  17.     //            当s[i - 1] 与 t[j - 1]相等时，dp[i][j]可以有两部分组成。
  18.     //            一部分是用s[i - 1]来匹配，那么个数为dp[i - 1][j - 1]。
  19.     //            一部分是不用s[i - 1]来匹配，个数为dp[i - 1][j]。
  20.     for (int i = 1; i <= s.length(); i++) {
  21.         for (int j = 1; j <= t.length(); j++) {
  22.             if (s.charAt(i - 1) == t.charAt(j - 1)) {
  23.                 dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]; // 注意时s中包含t，所以是 i - 1 而不是 j - 1
  24.             } else {
  25.                 dp[i][j] = dp[i - 1][j];
  26.             }
  27.         }
  28.     }
  30.     return dp[s.length()][t.length()];
  31. }