Java描述 LeetCode，115. Distinct Subsequences

大家好，我是河海哥，专注于后端，如果可以的话，想做一名code designer而不是普通的coder，一起见证河海哥的成长，您的评论与赞是我的最大动力。

Given two strings s and t, return the number of distinct subsequences of s which equals t.

A string’s subsequence is a new string formed from the original string by deleting some (can be none) of the characters without disturbing the remaining characters’ relative positions. (i.e., “ACE” is a subsequence of “ABCDE” while “AEC” is not).

It is guaranteed the answer fits on a 32-bit signed integer.

Example 1:

Input: s = "rabbbit", t = "rabbit"
Output: 3
Explanation:
As shown below, there are 3 ways you can generate "rabbit" from S.
rabbbit
rabbbit
rabbbit

Example 2:

Input: s = "babgbag", t = "bag"
Output: 5
Explanation:
As shown below, there are 5 ways you can generate "bag" from S.
babgbag
babgbag
babgbag
babgbag
babgbag

Constraints:

1 <= s.length, t.length <= 1000
s and t consist of English letters.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/distinct-subsequences

这道题，如果你和我一样有392的思路：https://blog.csdn.net/qq_41376740/article/details/121294391，这道题基本上列个表就可以写下去了。只不过这边的s是长字符串，t是短字符串。同样，按照之前的思路，我们dp几步先走下来：

• dp状态：dp[i][j]：以t[i]结尾的t[0:i]的序列 在以s[j]结尾的s[0:j]的序列中可以找到dp[i][j]个
• 状态转移方程：
  • t[i] == s[j] 的时候，就有点问题了，我一开始直接写的dp[i][j] = dp[i - 1][j - 1];后来看了答案，发现还有一种情况，比如s = rabb，t = rabbb，如果只考虑dp[i][j] = dp[i - 1][j - 1] 那么只有s=rabb,t=rab_b,t=ra_bb，也就是最后一个b是必选的，但是事实上还有t=rabb_这种情况，所以dp方程应该是dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1];
  • t[i] != s[j] 的时候，很好处理，dp[i][j] = dp[i][j - 1];
• 初始化：空字符串肯定是其他字符串的子串，所以dp[0][j] = 1;，非空字符串不是空字符串的子序列，所以第一列其他位置都是0；
• 确定遍历顺序：很好理解

public static int numDistinct(String s, String t) {
    int n = t.length();
    int m = s.length();

    int[][] dp = new int[n + 1][m + 1];
    for (int i = 0; i <= m; i++) {
        dp[0][i] = 1;
    }

    for (int i = 1; i < n + 1; i++) {
        for (int j = i; j < m + 1; j++) {
            if (t.charAt(i - 1) == s.charAt(j - 1)) {
                if (i == j) {
                    dp[i][j] = dp[i - 1][j - 1];
                }else {
                    dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1];
                }
            } else {
                dp[i][j] = dp[i][j - 1];
            }
        }
    }

    System.out.println(Arrays.deepToString(dp));
    return dp[n][m];
}
打表：
     r  a  b  b  b  i  t
 [1, 1, 1, 1, 1, 1, 1, 1], 
r[0, 1, 1, 1, 1, 1, 1, 1], 
a[0, 0, 1, 1, 1, 1, 1, 1], 
b[0, 0, 0, 1, 2, 3, 3, 3], 
b[0, 0, 0, 0, 1, 3, 3, 3], 
i[0, 0, 0, 0, 0, 0, 3, 3], 
t[0, 0, 0, 0, 0, 0, 0, 3]

代码可以用滚动数组优化，但是吧，我感觉除非做过，能上来就用滚动数组写吗？现在的我还做不到QAQ。

这道题其实不难，如果有之前的基础，做起来还是不那么难的，只是要考虑全面，我这里是有一个情况没有考虑到导致AC失败了。总的看来还行，至少比前面要好一些了。继续加油啊！河海哥，冲！如有错误还请指正，不胜感激，你的赞和评论是我最大的动力。一起加油！