LeetCode 115 不同的子序列 C++ 解法：3种动态规划状态转移方程对比与优化

LeetCode 115 不同的子序列3种动态规划解法深度剖析与C实现当我们在处理字符串匹配问题时动态规划往往能提供优雅而高效的解决方案。LeetCode 115题不同的子序列正是这样一个经典问题它要求我们统计字符串S的子序列中等于字符串T的不同子序列的个数。这个问题看似简单却蕴含着动态规划的多种实现思路和优化技巧。1. 问题理解与基础解法子序列的定义是在不改变字符相对顺序的情况下通过删除某些字符也可以不删除形成的新字符串。例如ace是abcde的子序列而aec则不是。对于这个问题我们需要计算S中有多少种不同的方式可以得到T。1.1 基础动态规划思路最直观的动态规划解法是使用二维DP数组其中dp[i][j]表示S的前i个字符中包含T的前j个字符的子序列数目。状态转移方程如下if (S[i-1] T[j-1]) { dp[i][j] dp[i-1][j] dp[i-1][j-1]; } else { dp[i][j] dp[i-1][j]; }完整实现代码如下int numDistinct(string S, string T) { int m S.length(), n T.length(); vectorvectorunsigned long dp(m1, vectorunsigned long(n1, 0)); // 初始化空字符串是任何字符串的子序列 for (int i 0; i m; i) dp[i][0] 1; for (int i 1; i m; i) { for (int j 1; j n; j) { if (S[i-1] T[j-1]) { dp[i][j] dp[i-1][j] dp[i-1][j-1]; } else { dp[i][j] dp[i-1][j]; } } } return dp[m][n]; }1.2 复杂度分析时间复杂度O(m×n)其中m和n分别是S和T的长度空间复杂度O(m×n)由二维DP数组决定2. 空间优化滚动数组技巧观察状态转移方程可以发现当前行的计算只依赖于上一行因此我们可以使用滚动数组将空间复杂度优化到O(n)。2.1 滚动数组实现int numDistinct(string S, string T) { int m S.length(), n T.length(); vectorunsigned long dp(n1, 0); dp[0] 1; // 空字符串 for (int i 1; i m; i) { // 需要从后往前更新避免覆盖还未使用的上一行数据 for (int j n; j 1; --j) { if (S[i-1] T[j-1]) { dp[j] dp[j-1]; } } } return dp[n]; }2.2 优化效果空间复杂度从O(m×n)降低到O(n)时间复杂度保持不变仍然是O(m×n)注意内层循环需要从后往前遍历避免覆盖还未使用的上一行数据3. 替代状态定义另一种动态规划思路除了上述常见解法外我们还可以采用另一种状态定义方式dp[i][j]表示S的前i个字符与T的前j个字符的匹配数。这种定义下状态转移方程略有不同。3.1 替代状态转移方程if (S[i-1] T[j-1]) { dp[i][j] dp[i-1][j-1] dp[i-1][j]; } else { dp[i][j] dp[i-1][j]; }虽然看起来与第一种方法相似但初始条件和边界处理有所不同int numDistinct(string S, string T) { int m S.length(), n T.length(); if (m n) return 0; vectorvectorunsigned long dp(m1, vectorunsigned long(n1, 0)); // 初始化空T是任何S的子序列 for (int i 0; i m; i) dp[i][0] 1; for (int i 1; i m; i) { for (int j 1; j min(i, n); j) { if (S[i-1] T[j-1]) { dp[i][j] dp[i-1][j-1] dp[i-1][j]; } else { dp[i][j] dp[i-1][j]; } } } return dp[m][n]; }3.2 方法对比特性基础二维DP滚动数组优化替代状态定义空间复杂度O(mn)O(n)O(mn)代码简洁性中等高中等边界条件处理简单中等较复杂适用场景通用大m小n需要特定分析4. 实战技巧与常见陷阱在实际编码面试中除了正确实现算法外还需要注意以下细节4.1 整数溢出问题由于结果可能非常大使用int类型可能会导致溢出。解决方案包括使用unsigned long或long long类型在每次更新dp值时检查是否超过限制对结果取模如果题目允许4.2 初始化技巧空字符串是任何字符串的子序列因此dp[i][0] 1当S的长度小于T时直接返回04.3 性能优化点提前终止当S的剩余字符不足以匹配T的剩余字符时可以提前结束循环内存访问优化按行或按列连续访问可以提高缓存命中率// 提前终止的优化示例 for (int i 1; i m; i) { // 只需要计算到min(i, n)即可 for (int j 1; j min(i, n); j) { // ...状态转移... } }4.4 测试用例设计验证代码时需要涵盖以下场景S和T完全相同的情况T是空字符串的情况S比T短的情况有多个匹配可能的情况如Srabbbit, Trabbit大字符串测试检查性能和溢出5. 扩展思考与变种问题掌握了基本解法后我们可以思考一些相关变种问题5.1 相似题目判断子序列LeetCode 392判断T是否是S的子序列最长公共子序列LeetCode 1143找两个字符串的最长公共子序列不同的子序列IILeetCode 940计算字符串的所有不同非空子序列数目5.2 进阶挑战如何修改算法以输出所有可能的子序列而不仅仅是计数如果允许字符替换操作如何计算将S转换为T的最小操作次数如何处理非常大的输入如字符串长度超过10^55.3 实际应用场景DNA序列比对代码差异分析自然语言处理中的字符串匹配在解决这类动态规划问题时关键在于准确理解状态定义和转移方程。不同的状态定义可能导致不同的实现复杂度和优化空间。对于面试准备建议不仅掌握基础解法还要理解各种优化技巧的适用场景和实现细节。