LeetCode 115: Distinct Subsequences ·

基本資料
#

難易度: hard 第一次嘗試：2026-07-19 來源：Day 38 learning note

學習脈絡
#

這篇是從 learning note 裡該 LeetCode 題目的段落重新整理出來的版本。我保留當天筆記中的修正點、比較點、容易犯錯的地方，並移除同一天其他非 LeetCode 主題，避免文章內容混題。

筆記中提到的相關提醒
#

LC 115: pass after repair
explain LC 115 with the exact counting state and the dp[i][0] = 1 base case
LC 115 vs LC 1143

當天筆記摘錄
#

Problem 1 - LC 115 Distinct Subsequences
#

Pattern: 2D DP on two prefixes with counting.

Why This Fits
#

The real question is:

how many ways can s[:i] form t[:j] by deleting characters from s?

That gives a counting table over:

source prefix of s
target prefix of t

Core State / Invariant
#

dp[i][j] = number of distinct subsequences of s[:i] that equal t[:j]

Base Cases
#

Empty target:

dp[i][0] = 1

Reason:

there is exactly one way to form the empty subsequence:
delete everything

Empty source but non-empty target:

dp[0][j] = 0 for j > 0

Reason:

an empty source cannot form a non-empty target

Transition
#

If the current characters match:

s[i - 1] == t[j - 1]
=> dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1]

Why two branches:

skip s[i - 1]
or use s[i - 1] to match the last character of t[:j]

If they do not match:

dp[i][j] = dp[i - 1][j]

Reason:

the current source character cannot help, so the only option is to skip it

Why This Works
#

At each source character, there are only two meaningful decisions:

do not use it
use it if and only if it matches the needed target character

The DP counts all valid choices without double counting because the two branches differ on whether the current source character is consumed.

Complexity
#

Time: O(m * n)
Space: O(m * n)

Can be compressed to:

Space: O(n)

Common Mistakes
#

forgetting that dp[i][0] = 1, not 0
using dp[i][j - 1] on mismatch
saying at least one way instead of exact count
mixing substring reasoning into a subsequence problem
losing track of which string is the source and which is the target

Strong Spoken Explanation
#

I define dp[i][j] as the number of ways the source prefix s[:i] can form the target prefix t[:j] as a subsequence. The empty target has exactly one formation from any source prefix, so dp[i][0] = 1. A non-empty target cannot be formed from an empty source, so dp[0][j] = 0 for j > 0. If the current characters match, I either skip the current source character or use it to match the current target character, so I add dp[i - 1][j] and dp[i - 1][j - 1]. If they do not match, I can only skip the current source character, so I carry dp[i - 1][j]. The answer is dp[len(s)][len(t)].

正確解法
#

上面的筆記保留了推理脈絡和當天需要修正的點。下面是我會提交的版本。

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        n = len(t)
        dp = [0] * (n + 1)
        dp[0] = 1

        for c in s:
            for j in range(n, 0, -1):
                if c == t[j - 1]:
                    dp[j] += dp[j - 1]

        return dp[n]