不同的子序列

Leetcode Link: 115. 不同的子序列 - 力扣（LeetCode）

题目

给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。

字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。 （例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）

题目数据保证答案符合 32 位带符号整数范围。

从暴力递归到动态规划

显然，该问题属于动态规划中的样本对应模型，因此我们需要讨论两个字符串端点 i, j 的可能性。

由于 t 字符串一定会全部出现在 s 字符串中，同时还要保证相对顺序不变，所以对于 s[0..i], t[0..j] 的当前位置 i，j，只有两种情况

1. 在 s[0...i-1] 上找 t[0..j]，即不 pick t[j]
2. pick t[j]，有前提，需要保证你能 pick 才行，即需要保证 strs[i] == target[j]

暴力递归

把上面的思路直接复现出来

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        return self.process(s, t, len(s)-1, len(t)-1)
    def process(self, strs, target, i, j): 
        # target的位置能走到这，说明之前的都能match上，返回1表示之前的所有选择是一个子序列
        if j < 0: 
            return 1
         # strs没了，但是target还有，咋着都匹配不上
        if i < 0 and j >= 0:
            return 0
        
        # 情况1：在后面寻找target的当前位
        p1 = self.process(strs, target, i-1, j)
        # 情况2：strs的当前为就是target的当前位（有前提）
        p2 = 0
        if strs[i] == target[j]:
            p2 = self.process(strs, target, i-1, j-1)
        return p1 + p2

记忆化搜索

没什么好说的，改改就行。

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        self.memo = [[None for _ in range(len(t))] for _ in range(len(s))]
        return self.process(s, t, len(s)-1, len(t)-1)
 
    def process(self, strs, target, i, j): 
        # target的位置能走到这，说明之前的都能match上，返回1表示之前的所有选择是一个子序列
        if j < 0: 
            return 1
         # strs没了，但是target还有，咋着都匹配不上
        if i < 0 and j >= 0:
            return 0
        
        if self.memo[i][j] != None:
            return self.memo[i][j]
 
        # 情况1：在后面寻找target的当前位
        p1 = self.process(strs, target, i-1, j)
        # 情况2：strs的当前为就是target的当前位（有前提）
        p2 = 0
        if strs[i] == target[j]:
            p2 = self.process(strs, target, i-1, j-1)
        self.memo[i][j] = p1 + p2
        return p1 + p2

动态规划

显然，只和 i, j 有关，所以改写成二维 dp

todo

启发和联系

不同于最长公共子序列，该问题的重点在于，t 字符串一定会全部出现在 s 字符串中才是满足条件的情况。

所以该问题的分类讨论情况更少

base case的选取标准