↓Skip to main content

【LeetCode 115】不同的子序列

·80 words·1 min
WFUing
Author
WFUing
A graduate who loves coding.
Table of Contents

  • 链接：https://leetcode.cn/problems/distinct-subsequences/description/

难点
#

在我二刷这道题的时候，卡着没做出来，画了 $dp[][]$ 数组，但是没有初始化，所以一直出错，直到看了题解。但是官方题解是从后往前遍历，我觉得并没有这个必要。

分析
#

主要还是分析三个问题：

  • dp数组表示什么
  • 如何初始化dp数组
  • 如何实现dp数组的更新

在这题里，$dp[i][j]$ 定义为 $s[i:]$ 的子序列中 $t[j:]$ 出现的个数。

按照对 $dp[i][j]$ 的定义，当 $j=0$ 时，空字符串是任意字符串的子串，所以都赋值 1。

如何实现dp数组的更新主要分为两种情况

代码
# 

class Solution {
    public int numDistinct(String s, String t) {
        int len1 = s.length(), len2 = t.length();
        int[][] dp = new int[len1+1][len2+1];
        for(int i=0;i<len1+1;i++) {
            dp[i][0]=1;
        }
        for(int i=1;i<=len1;i++) {
            for(int j=1;j<=len2;j++) {
                if(i<j) break;
                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[len1][len2];
    }
}