一、题目115. 不同的子序列 - 力扣LeetCode二、做题思路2.1 状态表示核心基础本题要求统计在s的子序列中t出现的不同个数。定义dp[i][j]表示t的前i个字符在s的前j个字符中出现的不同子序列个数。使用二维表行对应t的长度列对应s的长度便于分步累加。2.2 状态转移方程关键难点对于每个(i, j)有两种情况不选用s[j-1]继承s前j-1个字符的结果即dp[i][j-1]。若s[j-1] t[i-1]则还可以选择将当前字符匹配此时个数加上dp[i-1][j-1]即t的前i-1个字符在s前j-1个字符中的个数。2.3 初始化边界防护空字符串ti0在任意s前缀中只有一种匹配方式即不选任何字符因此dp[0][j] 1对所有j。其余dp[i][0]默认 0表示非空t在空s中无法匹配。2.4 填表顺序递推方向dp[i][j]依赖左方dp[i][j-1]和左上dp[i-1][j-1]因此从上到下i从 1 到row从左到右j从 1 到col遍历确保前置状态已就绪。2.5 返回值目标映射最终返回dp[row][col]row t.size()col s.size()即为完整t在完整s中出现的不同子序列个数。三、代码class Solution { public: int numDistinct(string s, string t) { int row t.size(); // 目标子串 t 的长度 int col s.size(); // 原字符串 s 的长度 // 1. 创建dp表 // dp[i][j] 表示 t 的前 i 个字符在 s 的前 j 个字符中出现的不同子序列个数 // 使用 double 类型防止中间结果溢出但最终结果保证在 int 范围内 vectorvectordouble dp(row 1, vectordouble(col 1, 0)); // 2. 初始化 // 空字符串 t即 i0在 s 的任意前缀包括空串中都只有一种出现方式不选任何字符 for (int j 0; j col; j) { dp[0][j] 1; } // 3. 填表顺序从上到下i 从 1 到 row从左到右j 从 1 到 col // 因为 dp[i][j] 依赖于 dp[i][j-1]左和 dp[i-1][j-1]左上 for (int i 1; i row; i) { for (int j 1; j col; j) { // 4. 状态转移方程核心 // 首先继承 s 的前 j-1 个字符中已经形成的个数即不使用 s[j-1] dp[i][j] dp[i][j - 1]; // 如果 s 的当前字符 s[j-1] 与 t 的当前字符 t[i-1] 相等 // 则还可以选择将 s[j-1] 与 t[i-1] 匹配此时个数加上 dp[i-1][j-1]即 t 的前 i-1 个字符在 s 的前 j-1 个字符中的个数 if (s[j - 1] t[i - 1]) { dp[i][j] dp[i - 1][j - 1]; } } } // 5. 返回值t 的完整串在 s 中出现的不同子序列个数 return (int)dp[row][col]; } };四、流程图五、题目44. 通配符匹配 - 力扣LeetCode六、做题思路6.1 状态表示核心基础本题要求判断字符串s是否与模式串p匹配其中?可匹配任意单个字符*可匹配任意长度含空的字符串。定义dp[i][j]表示s的前i个字符与p的前j个字符是否匹配true/false。多开一行一列便于处理空串边界。6.2 状态转移方程关键难点对于当前字符s[i]和p[j]从1开始若p[j] ?或s[i] p[j]则匹配与否取决于dp[i-1][j-1]。若p[j] *则*可匹配空串忽略它或匹配至少一个字符匹配空串看dp[i][j-1]匹配至少一个看dp[i-1][j]让*继续匹配s的剩余部分。因此转移为dp[i][j] dp[i-1][j] || dp[i][j-1]。其他情况为false。6.3 初始化边界防护dp[0][0] true空串匹配空模式。第一行dp[0][j]只有模式前缀全为*时才能匹配空串即连续的*对应true遇到非*后均为false。第一列dp[i][0]均为false非空s无法匹配空模式。6.4 填表顺序递推方向dp[i][j]依赖dp[i-1][j-1]、dp[i-1][j]和dp[i][j-1]因此从上到下i从 1 到row从左到右j从 1 到col遍历确保前置状态已就绪。6.5 返回值目标映射最终返回dp[row][col]即完整s与完整p是否匹配row s.size()col p.size()。七、代码class Solution { public: bool isMatch(string s, string p) { int row s.size(); // 原字符串长度 int col p.size(); // 模式串长度 // 1. 创建dp表多开一行一列便于处理空串边界 // dp[i][j] 表示 s 的前 i 个字符s[0..i-1]能否被 p 的前 j 个字符p[0..j-1]匹配 vectorvectorbool dp(row 1, vectorbool(col 1, false)); // 为了方便下标对齐在字符串前面添加一个占位符空格 // 这样 s[i] 对应原字符串的第 i-1 个字符p[j] 同理i 和 j 从 1 开始 s s; p p; // 2. 初始化 // dp[0][0] true空串匹配空模式 dp[0][0] true; // 处理空 s 匹配 p 的前缀只有连续的 * 才能匹配空串 // 因为 * 可以匹配空序列所以如果 p 的前 j 个字符都是 *则 dp[0][j] true // 一旦遇到非 *则后续都不匹配break for (int j 1; j col; j) { if (p[j] *) { dp[0][j] true; } else { break; } } // 3. 填表顺序从上到下i 从 1 到 row从左到右j 从 1 到 col // 因为 dp[i][j] 依赖于 dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1] for (int i 1; i row; i) { for (int j 1; j col; j) { // 4. 状态转移方程 // 情况一当前字符匹配s[i] p[j] 或 p[j] ? // 且 s 的前 i-1 个字符与 p 的前 j-1 个字符匹配则 dp[i][j] true if ((s[i] p[j] || p[j] ?) dp[i - 1][j - 1] true) { dp[i][j] true; } // 情况二p[j] * // * 可以匹配空串即忽略 *此时看 dp[i][j-1]让 * 匹配空 // 也可以匹配至少一个字符此时看 dp[i-1][j]让 * 匹配 s[i]并继续使用 * 匹配剩余 else if (p[j] *) { dp[i][j] dp[i - 1][j] || dp[i][j - 1]; } // 其余情况 dp[i][j] 保持 false } } // 5. 返回值dp[row][col] 表示完整 s 与完整 p 是否匹配 return dp[row][col]; } };八、流程图