115 Distinct Subsequences

https://leetcode.com/problems/distinct-subsequences/

solution

• 递归-分治-记忆化dfs

# S 每个字母就是两种状态：选或者不选
# https://leetcode.wang/leetcode-115-Distinct-Subsequences.html

时间复杂度：O() 空间复杂度：O()

• 动态规划

  • dp含义：dp[i][j], 以i-1结尾的子序列和以j-1结尾的子序列个数

  • dp推导：不同状态分别对待，如果相等时，用和不用

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

        for i in range(m+1):
            dp[i][0] = 1
        
        for i in range(1, m+1):
            for j in range(1, n+1):
                if s[i-1] == t[j-1]:
                    dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
                else:  # 根据dp含义, 不相等也要传播下去
                    dp[i][j] = dp[i-1][j]
        return dp[-1][-1]

时间复杂度：O() 空间复杂度：O()