题目

类型：动态规划
image.png

解题思路

代码

  1. class Solution {
  2.     public int numDistinct(String s, String t) {
  3.         memo = new int[s.length()][t.length()];
  4.         for (int[] row : memo) {
  5.             Arrays.fill(row, -1);
  6.         }
  7.         return dp(s, 0, t, 0);
  8.     }
  10.     int[][] memo;
  12.     // 定义：该函数返回 s[i..] 中的子序列 t[j..] 的数量
  13.     int dp(String s, int i, String t, int j) {
  14.         int m = s.length(), n = t.length();
  15.         if (j == n) {
  16.             // 子序列全部匹配完成
  17.             return 1;
  18.         }
  19.         if (n - j > m - i) {
  20.             // 待匹配子序列的长度不应该比字符串的长度还要短
  21.             return 0;
  22.         }
  23.         if (memo[i][j] != -1) {
  24.             // 已经计算过对应状态
  25.             return memo[i][j];
  26.         }
  27.         int res = 0;
  28.         // 状态转移方程
  29.         if (s.charAt(i) == t.charAt(j)) {
  30.             res += dp(s, i + 1, t, j + 1) + dp(s, i + 1, t, j);
  31.         } else {
  32.             res += dp(s, i + 1, t, j);
  33.         }
  34.         memo[i][j] = res;
  35.         return res;
  36.     }
  37. }