本文共 1242 字，大约阅读时间需要 4 分钟。
给定一个字符串 S 和一个字符串 T，计算在 S 的子序列中 T 出现的个数。子序列的定义是通过删除一些字符（也可以不删除），但不改变字符的相对位置所组成的新字符串。
我们可以使用动态规划的方法来解决这个问题。具体来说，我们定义一个二维数组 dp[i][j]，其中 i 表示 T 的前 i 个字符，j 表示 S 的前 j 个字符。dp[i][j] 表示前面已经匹配完 T 的第 i 个字符的情况下，当前已经匹配到 S 的第 j 个字符。
具体步骤如下：
dp[0][j]，dp[i][0] 为 1，其中 i 和 j 分别表示 T 和 S 的长度。dp[1][j] = dp[1][j-1] + 1；否则，dp[1][j] = dp[1][j-1]。dp[i][j] = dp[i][j-1] + dp[i-1][j-1]。dp[i][j] = dp[i][j-1]。最终，dp[tLength][sLength] 即为答案。
为了减少空间复杂度，可以将二维动态规划转换为一维数组 f，其中 f[i] 表示 T 的前 i 个字符已经匹配完的情况下，当前 S 的位置 j 的状态。具体实现步骤如下：
f 为大小 tLength + 1，并设置 f[0] = 1。f[1] += f[0]；否则，保持 f[1] 不变。i 逆向从 tLength 到 1 迭代。j 正向遍历 S 数串，对于每个位置，检查 s[j-1] 是否等于 t[i-1]。f[j] += f[j-1]，并更新 prev = f[j]。f[j] = f[j-1] 不变。另一种高效的方法是使用哈希表记录字符位置。具体步骤如下：
chPos，记录每个字符在 T 中的位置。chPos。ans 记录结果，其中 ans[i] 表示当前字符位置 i 的 T 子序列数。ch，更新 ans 数组，考虑其对后续字符位置的影响。这种方法通过预处理字符位置，避免了重复计数，提高了时间复杂度。
通过选用的方法，二维动态规划方法虽然直观，但空间复杂度较高；而优化后的一维动态规划方法或哈希表方法在时间和空间上表现更优。综合考虑实际问题规模和预处理成本，选择最合适的方法是关键。
通过以上方法，可以有效地解决问题，找到正确的子序列数量。
转载地址：http://ocnpz.baihongyu.com/