不同的子序列 -- 动规

115. 不同的子序列

class NumDistinct:
    """
    115. 不同的子序列
    https://leetcode.cn/problems/distinct-subsequences/description/
    """
    def solution1(self, s: str, t: str) -> int:
        """
        视角一，站在 t 的角度进行穷举 [盒子选择小球]
        t 中的若干字符就好像若干盒子
        s 中的若干字符就好像若干小球
        你需要做的就是给所有盒子都装一个小球

        M, N 分别代表 s, t 的长度
        状态个数【O(MN)】 * 函数本身的时间复杂度【O(M)】
        时间复杂度：O(MN) * O(M) = O(M^2 * N)
        空间复杂度：O(MN)

        :param s:
        :param t:
        :return:
        """
        self.memo = [[-1 for _ in range(len(t))] for _ in range(len(s))]
        return self.dp1(s, 0, t, 0)

    def dp1(self, s, i, t, j):
        """
        定义：s[i..] 的子序列中 t[j..] 出现的次数为 dp(s, i, t, j)
        :param s:
        :param i:
        :param t:
        :param j:
        :return:
        """
        # t 已经全部匹配完成
        if j == len(t):
            return 1

        #  s[i..] 比 t[j..] 还短，必然没有匹配的子序列
        if len(s) - i < len(t) - j:
            return 0

        #  查备忘录防止冗余计算
        if self.memo[i][j] != -1:
            return self.memo[i][j]

        res = 0
        # 站在 t 的角度进行穷举 [盒子选择小球]
        for k in range(i, len(s)):
            if s[k] == t[j]:
                res += self.dp1(s, k+1, t, j+1)

        self.memo[i][j] = res
        return res

    def solution2(self, s: str, t: str) -> int:
        """
        视角二，站在 s 的角度进行穷举 [小球选择盒子]

        M, N 分别代表 s, t 的长度
        状态个数【O(MN)】 * 函数本身的时间复杂度【O(1)】
        时间复杂度：O(MN) * O(1) = O(M * N)
        空间复杂度：O(MN)

        :param s:
        :param t:
        :return:
        """
        self.memo = [[-1 for _ in range(len(t))] for _ in range(len(s))]
        return self.dp2(s, 0, t, 0)

    def dp2(self, s, i, t, j):
        """
        定义：s[i..] 的子序列中 t[j..] 出现的次数为 dp(s, i, t, j)
        :param s:
        :param i:
        :param t:
        :param j:
        :return:
        """
        # t 已经全部匹配完成
        if j == len(t):
            return 1

        #  s[i..] 比 t[j..] 还短，必然没有匹配的子序列
        if len(s) - i < len(t) - j:
            return 0

        #  查备忘录防止冗余计算
        if self.memo[i][j] != -1:
            return self.memo[i][j]

        res = 0
        # 站在 s 的角度进行穷举 [小球选择盒子]
        if s[i] == t[j]:
            # 可以选择匹配和不匹配，所以两种情况需要叠加
            res += self.dp2(s, i + 1, t, j + 1) + self.dp2(s, i + 1, t, j)
        else:
            res += self.dp2(s, i + 1, t, j)

        self.memo[i][j] = res
        return res


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104