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
