难度: Hard
给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 109 + 7 取模。
示例 1：
输入：s = "rabbbit", t = "rabbit"输出：3解释： 如下所示, 有 3 种可以从 s 中得到"rabbit" 的方案。rabbbitrabbbitrabbbit
示例 2：
输入：s = "babgbag", t = "bag"输出：5解释： 如下所示, 有 5 种可以从 s 中得到"bag" 的方案。babgbagbabgbagbabgbagbabgbagbabgbag
提示：
1 <= s.length, t.length <= 1000s 和 t 由英文字母组成运行时间: 32 ms
内存: 0.0 MB
class Solution:
def numDistinct(self, s: str, t: str) -> int:
m, n = len(s), len(t)
if m < n: return 0
if m == n: return 1 if s == t else 0
dp = [0 for _ in range(n)]
for i in range(m):
for j in range(n-1, -1, -1):
if s[i] == t[j]:
dp[j] += 1 if j == 0 else dp[j-1]
return dp[-1]
这个题解使用动态规划的思路来解决问题。定义一个dp数组，其中dp[j]表示s的前i个字符中，t的前j个字符出现的次数。遍历s的每个字符，对于每个字符，倒序遍历t的字符。如果s[i]等于t[j]，那么更新dp[j]的值，dp[j]等于dp[j]加上dp[j-1]的值（如果j等于0，直接加1）。最后返回dp数组的最后一个元素即可。
时间复杂度: O(m*n)
空间复杂度: O(n)
class Solution:
def numDistinct(self, s: str, t: str) -> int:
m, n = len(s), len(t)
# 如果s的长度小于t，直接返回0
if m < n: return 0
# 如果s和t长度相等，判断是否相等，相等返回1，不相等返回0
if m == n: return 1 if s == t else 0
# 初始化dp数组，长度为n，初始值为0
dp = [0 for _ in range(n)]
# 遍历s的每个字符
for i in range(m):
# 倒序遍历t的每个字符
for j in range(n-1, -1, -1):
# 如果s[i]等于t[j]
if s[i] == t[j]:
# 如果j等于0，dp[j]加1，否则dp[j]加上dp[j-1]的值
dp[j] += 1 if j == 0 else dp[j-1]
# 返回dp数组的最后一个元素
return dp[-1]
在这个问题中，我们使用一维数组代替二维数组主要是为了节省空间。如果使用二维数组，我们需要一个大小为m*n的数组来存储状态，其中m和n分别是字符串s和t的长度。然而，观察到每次更新dp数组时，只需要当前行和前一行的数据。因此，通过使用一维数组并以适当的方式更新它，我们只保留必需的信息，从而将空间复杂度从O(m*n)减少到O(n)。
在动态规划的更新过程中，从后向前更新dp数组是为了保证在计算dp[j]的值时，所依赖的dp[j-1]的值是上一轮循环的结果，即前一个状态的值。如果从前向后更新，那么在计算dp[j]时，dp[j-1]可能已经被更新为当前轮的值，这会导致错误地重复计算，从而使得最终结果不正确。因此，倒序更新确保了每个状态是基于正确的前一状态进行计算的。
如果s和t的长度相等，那么问题简化为判断两个字符串是否完全相同。因为动态规划的目的是计算s的子序列中t出现的次数，如果长度相同，那么t只有在完全匹配s的情况下才能被视为一个子序列。这种情况下，没有必要进行复杂的动态规划计算，直接比较两个字符串是否相等即可。如果相等，结果为1；如果不相等，结果为0。这种方法更直接且效率更高。
在动态规划中，dp[j]代表s的前i个字符中，t的前j个字符作为子序列出现的次数。当我们在s中找到一个与t中第j个字符相匹配的字符时，这个字符可以独立形成一个新的子序列（如果j为0），或者它可以扩展所有以t的前j-1个字符结尾的子序列。因此，dp[j]增加dp[j-1]的值表示当前字符可以添加到所有以t的前j-1个字符结尾的子序列末尾，从而形成新的子序列。这是一个累积过程，其中每个匹配都可能增加多个有效子序列的计数。