Distinct Subsequences烟雨迷楼1

《Distinct Subsequences：C++实现解析》 在编程竞赛或算法设计中，"Distinct Subsequences" 是一个常见的问题，它涉及到动态规划（Dynamic Programming）这一重要概念。这道题目要求我们找出一个主串（字符串S）中所有是另一个匹配串（字符串T）的子序列的个数。这里的子序列是指在不改变字符顺序的情况下，通过删除原字符串的部分字符形成的序列。与子串不同，子序列允许跳跃字符。 动态规划是解决此类问题的有效方法，因为它能够将复杂问题分解为更小的子问题，并存储子问题的解以避免重复计算。对于 "Distinct Subsequences"，我们可以定义一个二维数组 dp[i][j]，表示匹配串 T 的前 i 个字符与主串 S 的前 j 个字符匹配成功的个数。 递推公式如下： 1. 当 t[i - 1] == s[j - 1] 时，即当前字符相等，那么 dp[i][j] 就等于在不考虑当前字符 s[j - 1] 的情况下（即 dp[i][j - 1]）加上在考虑当前字符 s[j - 1] 并且 t[i - 1] 也匹配上的情况下（即 dp[i - 1][j - 1]）的子序列个数，即 dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1]。 2. 当 t[i - 1] != s[j - 1] 时，当前字符不相等，那么 dp[i][j] 只能等于 dp[i][j - 1]，因为不匹配的字符不能影响之前匹配的子序列。 根据这个思路，我们可以编写如下的 C++ 代码： ```cpp int judge(string s, string t) { vector<vector<int>> dp(t.size() + 1, vector<int>(s.size() + 1, 0)); int i, j; // 初始化第一列，表示空串与任意串的匹配次数为1 for (i = 0; i <= s.size(); i++) dp[0][i] = 1; // 动态规划填表 for (i = 1; i <= t.size(); i++) { for (j = i; j <= s.size(); j++) { if (t[i - 1] == s[j - 1]) dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1]; else dp[i][j] = dp[i][j - 1]; } } // 返回最后的结果，即匹配串T与主串S的子序列个数 return dp[t.size()][s.size()]; } ``` 这段代码首先初始化了 dp 数组的第一列，表示空串与任何字符串匹配的次数为 1。然后通过两层循环，逐一对主串和匹配串的每个字符进行比较，根据递推公式填充 dp 数组。返回 dp[t.size()][s.size()]，即为答案。 这个算法的时间复杂度是 O(mn)，其中 m 和 n 分别是主串 S 和匹配串 T 的长度。空间复杂度也是 O(mn)，因为我们需要一个二维数组来存储所有的中间结果。在实际应用中，如果字符串长度非常大，可能会面临内存效率的问题，但这是解决此问题的基本方法，优化通常需要对算法有更深入的理解和技巧。 "Distinct Subsequences" 题目不仅考察了动态规划的运用，还涉及到了字符串处理和递推关系的建立，是提高编程能力、锻炼算法思维的良好实践。理解并掌握这种算法，对于提升编程技能和解决实际问题具有重要意义。