线性动态规划：不同的子序列

字数 2313 2025-10-26 11:43:54

线性动态规划：不同的子序列

题目描述
给定一个字符串 s 和一个字符串 t，计算在 s 的子序列中 t 出现的个数。
字符串的一个子序列是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）
题目数据保证答案符合 32 位带符号整数范围。

示例
输入：s = "rabbbit", t = "rabbit"
输出：3
解释：
如下所示，有 3 种可以从 s 中选出 "rabbit" 的方案。
rabbbit
rabbbit
rabbbit

解题过程

1. 问题分析
我们需要统计字符串 s 中有多少个子序列等于字符串 t。
关键点：子序列不要求连续，但必须保持字符的相对顺序。
思路：使用动态规划，定义 dp[i][j] 表示 s 的前 i 个字符中，t 的前 j 个字符出现的子序列个数。

2. 状态定义
设 dp[i][j] 表示 s[0..i-1] 的子序列中 t[0..j-1] 出现的个数。

i 的取值范围：0 到 len(s)
j 的取值范围：0 到 len(t)

3. 状态转移方程
考虑 s 的第 i 个字符 s[i-1] 和 t 的第 j 个字符 t[j-1]：

如果 s[i-1] != t[j-1]：
当前字符不匹配，那么 s[i-1] 不能用于匹配 t[j-1]，只能忽略 s[i-1]，继承 s[0..i-2] 中匹配 t[0..j-1] 的结果：
dp[i][j] = dp[i-1][j]
如果 s[i-1] == t[j-1]：
有两种选择：
1. 使用 s[i-1] 匹配 t[j-1]：那么需要看 s[0..i-2] 中匹配 t[0..j-2] 的个数，即 dp[i-1][j-1]
2. 不使用 s[i-1] 匹配 t[j-1]：那么继承 s[0..i-2] 中匹配 t[0..j-1] 的个数，即 dp[i-1][j]
  因此：dp[i][j] = dp[i-1][j-1] + dp[i-1][j]

4. 初始化

当 j = 0（即 t 为空字符串）时，空字符串是任何字符串的子序列，且只有一种方式（删除所有字符），所以 dp[i][0] = 1（对任意 i）
当 i = 0 且 j > 0（即 s 为空但 t 非空）时，无法匹配，所以 dp[0][j] = 0

5. 计算顺序
按 i 从 0 到 len(s)，j 从 0 到 len(t) 的顺序计算。
注意：当 j > i 时，t 比 s 长，不可能匹配，但我们的递推公式在 j > i 时依然正确（因为会继承上一行的值，最终为 0）。

6. 结果
最终结果为 dp[len(s)][len(t)]

示例推导（s = "rabbbit", t = "rabbit"）
初始化：
dp[i][0] = 1（第一列全为 1）
dp[0][j] = 0（j>0，第一行除 dp[0][0] 外为 0）

逐步计算（行列对应 s 和 t 的字符索引）：

i=1, s[0]='r'：
j=1, t[0]='r'：匹配，dp[1][1] = dp[0][0] + dp[0][1] = 1 + 0 = 1
其他 j>1 为 0（继承上一行）
i=2, s[1]='a'：
j=1, t[0]='r'：不匹配，继承 dp[1][1]=1
j=2, t[1]='a'：匹配，dp[2][2] = dp[1][1] + dp[1][2] = 1 + 0 = 1
i=3, s[2]='b'：
j=1：不匹配，继承 dp[2][1]=1
j=2：不匹配，继承 dp[2][2]=1
j=3, t[2]='b'：匹配，dp[3][3] = dp[2][2] + dp[2][3] = 1 + 0 = 1
i=4, s[3]='b'：
j=1：继承 1
j=2：继承 1
j=3：匹配 'b'，dp[4][3] = dp[3][2] + dp[3][3] = 0 + 1 = 1
j=4, t[3]='b'：匹配，dp[4][4] = dp[3][3] + dp[3][4] = 1 + 0 = 1
i=5, s[4]='b'：
j=3：匹配 'b'，dp[5][3] = dp[4][2] + dp[4][3] = 0 + 1 = 1
j=4：匹配 'b'，dp[5][4] = dp[4][3] + dp[4][4] = 1 + 1 = 2
j=5, t[4]='i'：不匹配，继承 dp[4][5]=0
i=6, s[5]='i'：
j=5：匹配 'i'，dp[6][5] = dp[5][4] + dp[5][5] = 2 + 0 = 2
j=6, t[5]='t'：不匹配，继承 dp[5][6]=0
i=7, s[6]='t'：
j=6：匹配 't'，dp[7][6] = dp[6][5] + dp[6][6] = 2 + 0 = 3

最终结果：dp[7][6] = 3，与示例一致。

线性动态规划：不同的子序列题目描述给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。字符串的一个子序列是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）题目数据保证答案符合 32 位带符号整数范围。示例输入：s = "rabbbit", t = "rabbit" 输出：3 解释：如下所示，有 3 种可以从 s 中选出 "rabbit" 的方案。 rabbbit rabbbit rabbbit 解题过程 1. 问题分析我们需要统计字符串 s 中有多少个子序列等于字符串 t 。关键点：子序列不要求连续，但必须保持字符的相对顺序。思路：使用动态规划，定义 dp[i][j] 表示 s 的前 i 个字符中， t 的前 j 个字符出现的子序列个数。 2. 状态定义设 dp[i][j] 表示 s[0..i-1] 的子序列中 t[0..j-1] 出现的个数。 i 的取值范围：0 到 len(s) j 的取值范围：0 到 len(t) 3. 状态转移方程考虑 s 的第 i 个字符 s[i-1] 和 t 的第 j 个字符 t[j-1] ：如果 s[i-1] != t[j-1] ：当前字符不匹配，那么 s[i-1] 不能用于匹配 t[j-1] ，只能忽略 s[i-1] ，继承 s[0..i-2] 中匹配 t[0..j-1] 的结果： dp[i][j] = dp[i-1][j] 如果 s[i-1] == t[j-1] ：有两种选择：使用 s[i-1] 匹配 t[j-1] ：那么需要看 s[0..i-2] 中匹配 t[0..j-2] 的个数，即 dp[i-1][j-1] 不使用 s[i-1] 匹配 t[j-1] ：那么继承 s[0..i-2] 中匹配 t[0..j-1] 的个数，即 dp[i-1][j] 因此： dp[i][j] = dp[i-1][j-1] + dp[i-1][j] 4. 初始化当 j = 0 （即 t 为空字符串）时，空字符串是任何字符串的子序列，且只有一种方式（删除所有字符），所以 dp[i][0] = 1 （对任意 i ）当 i = 0 且 j > 0 （即 s 为空但 t 非空）时，无法匹配，所以 dp[0][j] = 0 5. 计算顺序按 i 从 0 到 len(s) ， j 从 0 到 len(t) 的顺序计算。注意：当 j > i 时， t 比 s 长，不可能匹配，但我们的递推公式在 j > i 时依然正确（因为会继承上一行的值，最终为 0）。 6. 结果最终结果为 dp[len(s)][len(t)] 示例推导（s = "rabbbit", t = "rabbit"）初始化： dp[ i][ 0 ] = 1（第一列全为 1） dp[ 0][ j] = 0（j>0，第一行除 dp[ 0][ 0 ] 外为 0）逐步计算（行列对应 s 和 t 的字符索引）： i=1, s[ 0 ]='r'： j=1, t[ 0]='r'：匹配，dp[ 1][ 1] = dp[ 0][ 0] + dp[ 0][ 1 ] = 1 + 0 = 1 其他 j>1 为 0（继承上一行） i=2, s[ 1 ]='a'： j=1, t[ 0]='r'：不匹配，继承 dp[ 1][ 1 ]=1 j=2, t[ 1]='a'：匹配，dp[ 2][ 2] = dp[ 1][ 1] + dp[ 1][ 2 ] = 1 + 0 = 1 i=3, s[ 2 ]='b'： j=1：不匹配，继承 dp[ 2][ 1 ]=1 j=2：不匹配，继承 dp[ 2][ 2 ]=1 j=3, t[ 2]='b'：匹配，dp[ 3][ 3] = dp[ 2][ 2] + dp[ 2][ 3 ] = 1 + 0 = 1 i=4, s[ 3 ]='b'： j=1：继承 1 j=2：继承 1 j=3：匹配 'b'，dp[ 4][ 3] = dp[ 3][ 2] + dp[ 3][ 3 ] = 0 + 1 = 1 j=4, t[ 3]='b'：匹配，dp[ 4][ 4] = dp[ 3][ 3] + dp[ 3][ 4 ] = 1 + 0 = 1 i=5, s[ 4 ]='b'： j=3：匹配 'b'，dp[ 5][ 3] = dp[ 4][ 2] + dp[ 4][ 3 ] = 0 + 1 = 1 j=4：匹配 'b'，dp[ 5][ 4] = dp[ 4][ 3] + dp[ 4][ 4 ] = 1 + 1 = 2 j=5, t[ 4]='i'：不匹配，继承 dp[ 4][ 5 ]=0 i=6, s[ 5 ]='i'： j=5：匹配 'i'，dp[ 6][ 5] = dp[ 5][ 4] + dp[ 5][ 5 ] = 2 + 0 = 2 j=6, t[ 5]='t'：不匹配，继承 dp[ 5][ 6 ]=0 i=7, s[ 6 ]='t'： j=6：匹配 't'，dp[ 7][ 6] = dp[ 6][ 5] + dp[ 6][ 6 ] = 2 + 0 = 3 最终结果：dp[ 7][ 6 ] = 3，与示例一致。