定义 dp[0..n][0..m] 初始化为0
for i from 0 to n:
    dp[i][0] = 1
for i from 1 to n:
    for j from 1 to m:
        dp[i][j] = dp[i-1][j]
        if s[i] == t[j]:
            dp[i][j] = dp[i][j] + dp[i-1][j-1]
        结果取模
返回 dp[n][m]

初始化 dp[0..m]，dp[0]=1, dp[1..m]=0
for i from 1 to n:
    for j from m downto 1:
        if s[i] == t[j]:
            dp[j] = (dp[j] + dp[j-1]) % MOD
        # 如果不等，dp[j]保持不变（即上一轮的dp[j]）

统计不同子序列的个数（带限制版本） 题目描述 给定一个字符串 s 和一个目标字符串 t，你需要计算在 s 的子序列中等于 t 的不同子序列的个数。注意，这里的“子序列”指的是从原始字符串中删除一些字符（也可以不删除）后，剩下的字符在不改变相对顺序的情况下组成的新字符串。即使两个子序列在 s 中占据的位置（下标）不同，但只要构成的字符串相同，就算作相同的子序列。你需要统计的是等于 t 的、不同的子序列个数。 输入格式 ：两个字符串 s 和 t，长度分别为 n 和 m，其中 1 <= m <= n <= 1000。 输出格式 ：一个整数，表示 s 的子序列中等于 t 的子序列个数。由于结果可能很大，请返回结果对 10^9 + 7 取模的值。 例如： s = "rabbbit", t = "rabbit" 输出：3 解释：s 中有三种方式可以得到 "rabbit"： rabb b it ra b bbit rab b bit （用空格和加粗表示选取的字符位置） 解题过程 这是一个经典的序列匹配问题，但要求统计不同的匹配方式（即使匹配位置不同，只要对应相同的子序列就算一种）。由于我们统计的是不同的子序列（即匹配的字符串相同就算一种），所以这实际上问的是：s 中有多少种 不同 的方法（选取字符的位置集合）可以组成 t。由于我们统计的是不同的 位置选择 ，即使最终得到的字符串相同，但选取的位置不同，也算作不同的子序列。然而，题目中“不同的子序列”指的是字符串不同，而不是选取的位置不同。但在这个经典问题中，通常我们计算的是 不同的位置选择 的数量，即有多少种不同的下标选择方式，使得选出的字符序列恰好等于 t。题目描述中“不同的子序列”可能有些歧义，但在算法竞赛和面试中，这个问题通常定义为“统计 s 的子序列中等于 t 的个数”，而“个数”是指不同的选取方式的数量（即使得到的字符串相同，但选取的下标组合不同也算不同的方式）。为了明确，我们采用标准定义： 求 s 中有多少种不同的下标选择方案，使得选出的字符按顺序连起来等于 t 。 1. 问题分析 我们有两个字符串： s[ 1..n ] （假设索引从1开始，方便讲解） t[ 1..m ] 我们需要从 s 中选出一些字符（保持原有顺序），形成一个长度为 m 的子序列，使其恰好等于 t。问有多少种选法。 2. 暴力思路 一种最直接的方法是枚举 s 中所有长度为 m 的子序列（通过递归或回溯），检查它是否等于 t。这样的子序列有 C(n, m) 个，当 n 较大时（如 1000）无法承受。我们需要一个高效的方法。 3. 动态规划状态定义 这是一个典型的“两个序列”匹配问题，可以使用二维动态规划。定义状态 dp[ i][ j] 表示：考虑 s 的前 i 个字符（s[ 1..i]）和 t 的前 j 个字符（t[ 1..j]），在 s[ 1..i] 的子序列中等于 t[ 1..j ] 的个数。 最终答案就是 dp[ n][ m ]。 4. 状态转移方程 我们考虑如何从已知的状态推导出 dp[ i][ j ]。分两种情况讨论，取决于我们是否使用 s 的第 i 个字符来匹配 t 的第 j 个字符。 情况1：不使用 s[ i] 来匹配 t[ j] 这意味着我们在 s[ 1..i-1] 中就已经找到了所有匹配 t[ 1..j] 的方式。所以这部分的数量是 dp[ i-1][ j ]。 情况2：使用 s[ i] 来匹配 t[ j] 这有一个前提：s[ i] 必须等于 t[ j]。如果相等，那么我们可以用 s[ i] 去匹配 t[ j]，然后问题就转化为：在 s[ 1..i-1] 中找子序列匹配 t[ 1..j-1]。所以这部分的数量是 dp[ i-1][ j-1]（前提是 s[ i] == t[ j ]）。 综合两种情况： 如果 s[ i] != t[ j]，那么我们只能不使用 s[ i]，所以 dp[ i][ j] = dp[ i-1][ j ]。 如果 s[ i] == t[ j]，那么我们有两种选择：用 s[ i] 或者不用 s[ i]。所以 dp[ i][ j] = dp[ i-1][ j] + dp[ i-1][ j-1 ]。 5. 边界条件 我们需要初始化 dp 数组，使得转移能够正确进行。 当 j = 0 时，t 的前 0 个字符是空串。空串是任何字符串的子序列，而且只有一种方式（什么都不选）。所以对于任意 i (0 <= i <= n)，dp[ i][ 0 ] = 1。 当 i = 0 且 j > 0 时，s 是空串，而 t 非空，显然无法匹配。所以 dp[ 0][ j ] = 0 (j > 0)。 当 i=0, j=0 时，两个空串匹配，dp[ 0][ 0 ] = 1。 6. 递推计算 我们可以按照 i 从 0 到 n，j 从 0 到 m 的顺序计算 dp[ i][ j]。注意，当 i < j 时，s 的前 i 个字符长度小于 t 的前 j 个字符，显然不可能匹配，dp[ i][ j] = 0。但这其实在递推中会自然得出（因为 dp[ i-1][ j] 和 dp[ i-1][ j-1 ] 可能为0）。 伪代码： 7. 示例推演 以 s = "rabbbit", t = "rabbit" 为例（长度 n=7, m=6）。为直观，我们用字符数组，索引从1开始。 s: 1:r 2:a 3:b 4:b 5:b 6:i 7:t t: 1:r 2:a 3:b 4:b 5:i 6:t 初始化 dp[ i][ 0]=1, dp[ 0][ j ]=0 (j>0)。 i=1 (s[ 1 ]='r'): j=1: s[ 1]=='r' -> dp[ 1][ 1] = dp[ 0][ 1] + dp[ 0][ 0 ] = 0+1=1 j>1: 均为0 i=2 (s[ 2 ]='a'): j=1: s[ 2]!='r' -> dp[ 2][ 1]=dp[ 1][ 1 ]=1 j=2: s[ 2]=='a' -> dp[ 2][ 2]=dp[ 1][ 2]+dp[ 1][ 1 ]=0+1=1 j>2: 0 i=3 (s[ 3 ]='b'): j=1: !='r' -> dp[ 3][ 1]=dp[ 2][ 1 ]=1 j=2: !='a' -> dp[ 3][ 2]=dp[ 2][ 2 ]=1 j=3: =='b' -> dp[ 3][ 3]=dp[ 2][ 3]+dp[ 2][ 2 ]=0+1=1 j=4: !='b' (注意t[ 4]是'b')? 不，t[ 4]是'b'，但此时j=4，s[ 3]=='b'==t[ 4]? 不对，t[ 4]是第4个字符，但我们在j=4时，比较的是t[ 4]='b'，s[ 3]=='b'相等，但dp[ 2][ 3]和dp[ 2][ 4]? 我们按照公式，当s[ i]==t[ j]时，用dp[ i-1][ j-1]。这里j=4，s[ 3]==t[ 4]成立，所以dp[ 3][ 4]=dp[ 2][ 4]+dp[ 2][ 3]=0+0=0。因为dp[ 2][ 4]和dp[ 2][ 3 ]都是0。 继续计算... 为了节省篇幅，我们直接给出最终dp表的一部分关键值： dp[ 3][ 3 ]=1 (匹配"rab") dp[ 4][ 4]=? 当i=4,s[ 4]='b'，j=4,t[ 4]='b'相等，dp[ 4][ 4]=dp[ 3][ 4]+dp[ 3][ 3 ]=0+1=1 dp[ 5][ 4]=? i=5,s[ 5]='b', j=4,t[ 4]='b'，dp[ 5][ 4]=dp[ 4][ 4]+dp[ 4][ 3 ]=1+1=2 dp[ 6][ 5]=? i=6,s[ 6]='i', j=5,t[ 5]='i'，dp[ 6][ 5]=dp[ 5][ 5]+dp[ 5][ 4 ]=0+2=2 dp[ 7][ 6]=? i=7,s[ 7]='t', j=6,t[ 6]='t'，dp[ 7][ 6]=dp[ 6][ 6]+dp[ 6][ 5]=0+2=2? 等一下，这里dp[ 6][ 6]应该是0，因为t[ 6]='t'，s[ 6]='i'不等，所以dp[ 6][ 6]=dp[ 5][ 6]=0。然后dp[ 6][ 5]=2，所以dp[ 7][ 6 ]=0+2=2？但答案是3。我们发现计算有误。 仔细检查，t的长度是6，我们的dp表应该是dp[ 7][ 6]。实际上，在i=7时，s[ 7]='t'匹配t[ 6]='t'，所以dp[ 7][ 6]=dp[ 6][ 6] + dp[ 6][ 5]。dp[ 6][ 6]表示不用s[ 7]时，s[ 1..6]匹配t[ 1..6]的数量，这个应该是0（因为s[ 1..6]="rabbbi"，最后是i不是t）。dp[ 6][ 5]表示s[ 1..6]匹配t[ 1..5]的数量，我们之前算得是2。所以dp[ 7][ 6]=0+2=2，但答案是3，说明dp[ 6][ 5 ]应该为3才对。 我们重新仔细推导一遍： 建立dp表，行i从0到7，列j从0到6。 初始化： dp[ i][ 0 ]=1 for all i. dp[ 0][ j ]=0 for j>0. i=1, s[ 1 ]=r j=1: s[ 1]==t[ 1]? r==r -> dp[ 1][ 1]=dp[ 0][ 1]+dp[ 0][ 0 ]=0+1=1 j=2..6: dp[ 1][ j]=dp[ 0][ j]=0 (因为s[ 1]!=t[ j ] for j>=2) i=2, s[ 2 ]=a j=1: s[ 2]!=t[ 1] -> dp[ 2][ 1]=dp[ 1][ 1 ]=1 j=2: s[ 2]==t[ 2]? a==a -> dp[ 2][ 2]=dp[ 1][ 2]+dp[ 1][ 1 ]=0+1=1 j=3..6: dp[ 2][ j]=dp[ 1][ j ]=0 i=3, s[ 3 ]=b j=1: !=r -> dp[ 3][ 1]=dp[ 2][ 1 ]=1 j=2: !=a -> dp[ 3][ 2]=dp[ 2][ 2 ]=1 j=3: s[ 3]==t[ 3]? b==b -> dp[ 3][ 3]=dp[ 2][ 3]+dp[ 2][ 2 ]=0+1=1 j=4: s[ 3]==t[ 4]? b==b -> dp[ 3][ 4]=dp[ 2][ 4]+dp[ 2][ 3 ]=0+0=0 j=5: !=i -> dp[ 3][ 5]=dp[ 2][ 5 ]=0 j=6: !=t -> dp[ 3][ 6]=dp[ 2][ 6 ]=0 i=4, s[ 4 ]=b j=1: !=r -> dp[ 4][ 1]=dp[ 3][ 1 ]=1 j=2: !=a -> dp[ 4][ 2]=dp[ 3][ 2 ]=1 j=3: s[ 4]==t[ 3]? b==b -> dp[ 4][ 3]=dp[ 3][ 3]+dp[ 3][ 2 ]=1+1=2 j=4: s[ 4]==t[ 4]? b==b -> dp[ 4][ 4]=dp[ 3][ 4]+dp[ 3][ 3 ]=0+1=1 j=5: !=i -> dp[ 4][ 5]=dp[ 3][ 5 ]=0 j=6: !=t -> dp[ 4][ 6]=dp[ 3][ 6 ]=0 i=5, s[ 5 ]=b j=1: !=r -> dp[ 5][ 1]=dp[ 4][ 1 ]=1 j=2: !=a -> dp[ 5][ 2]=dp[ 4][ 2 ]=1 j=3: s[ 5]==t[ 3]? b==b -> dp[ 5][ 3]=dp[ 4][ 3]+dp[ 4][ 2 ]=2+1=3 j=4: s[ 5]==t[ 4]? b==b -> dp[ 5][ 4]=dp[ 4][ 4]+dp[ 4][ 3 ]=1+2=3 j=5: !=i -> dp[ 5][ 5]=dp[ 4][ 5 ]=0 j=6: !=t -> dp[ 5][ 6]=dp[ 4][ 6 ]=0 i=6, s[ 6 ]=i j=1: !=r -> dp[ 6][ 1]=dp[ 5][ 1 ]=1 j=2: !=a -> dp[ 6][ 2]=dp[ 5][ 2 ]=1 j=3: !=b -> dp[ 6][ 3]=dp[ 5][ 3 ]=3 j=4: !=b -> dp[ 6][ 4]=dp[ 5][ 4 ]=3 j=5: s[ 6]==t[ 5]? i==i -> dp[ 6][ 5]=dp[ 5][ 5]+dp[ 5][ 4 ]=0+3=3 j=6: !=t -> dp[ 6][ 6]=dp[ 5][ 6 ]=0 i=7, s[ 7 ]=t j=1: !=r -> dp[ 7][ 1]=dp[ 6][ 1 ]=1 j=2: !=a -> dp[ 7][ 2]=dp[ 6][ 2 ]=1 j=3: !=b -> dp[ 7][ 3]=dp[ 6][ 3 ]=3 j=4: !=b -> dp[ 7][ 4]=dp[ 6][ 4 ]=3 j=5: !=i -> dp[ 7][ 5]=dp[ 6][ 5 ]=3 j=6: s[ 7]==t[ 6]? t==t -> dp[ 7][ 6]=dp[ 6][ 6]+dp[ 6][ 5 ]=0+3=3 最终 dp[ 7][ 6 ] = 3，与答案一致。 8. 空间优化 观察状态转移方程，dp[ i][ j] 只依赖于 dp[ i-1][ j] 和 dp[ i-1][ j-1]。所以我们可以使用滚动数组，将第一维压缩，只保留一维数组 dp[ 0..m]。但注意，由于我们需要用到上一行的 dp[ j-1]，所以在更新 dp[ j ] 时，应该从 j=m 到 1 逆序更新，以免覆盖上一行的值。 伪代码： 注意：当 s[ i] != t[ j] 时，dp[ j] 保持不变，这正好对应了 dp[ i][ j] = dp[ i-1][ j]。因为逆序更新，dp[ j ] 在本次循环中还没有被更新，所以它仍然是上一轮（i-1）的值。 9. 总结 这个问题的核心在于定义 dp[ i][ j] 为 s 前 i 个字符中匹配 t 前 j 个字符的子序列个数。状态转移分为使用或不使用 s[ i ] 两种。初始化时，匹配空串有1种方式。最终通过递推得到结果。空间可以优化到 O(m)。注意取模。 这个算法的时间复杂度是 O(n* m)，空间复杂度 O(m)，可以处理 n, m 达到几千的问题。