115. 不同的子序列

这道题的核心在于理解状态转移方程的设计。定义 dp[i][j] 为 s[0..i-1] 中 t[0..j-1] 作为子序列出现的次数。

状态转移需要分情况讨论：当 s[i-1] == t[j-1] 时，可以选择匹配这对字符，方案数来自 dp[i-1][j-1]；也可以选择不匹配，方案数来自 dp[i-1][j]。两者相加即为当前状态。当字符不相等时，只能继承 dp[i-1][j] 的值。

初始化方面，dp[i][0] = 1 表示空串 t 是任何字符串 s 的子序列，且恰好有一种方式（删除所有字符）。这一行初始化为 1 而非 0 是容易疏忽的地方。

关于取模运算的一个细节：C++ 中整数溢出属于未定义行为，不会抛出异常。先加后模的写法 (a + b) % MOD 在溢出后取模，结果可能因编译器实现而异。更稳妥的做法是先分别取模再相加：

class Solution {
public:
    int numDistinct(string src, string pat) {
        const int MOD = 1000000007;
        int lenS = src.length();
        int lenP = pat.length();
        vector<vector<int>> memo(lenS + 1, vector<int>(lenP + 1, 0));
        
        for (int i = 0; i <= lenS; ++i) {
            memo[i][0] = 1;
        }
        
        for (int i = 1; i <= lenS; ++i) {
            for (int j = 1; j <= lenP; ++j) {
                if (src[i - 1] == pat[j - 1]) {
                    memo[i][j] = (memo[i - 1][j - 1] % MOD + memo[i - 1][j] % MOD) % MOD;
                } else {
                    memo[i][j] = memo[i - 1][j];
                }
            }
        }
        return memo[lenS][lenP];
    }
};

583. 两个字符串的删除操作

本题可转化为求最长公共子序列（LCS）的变体。两个字符串通过删除操作变得相同，等价于保留它们的最长公共子序列，删除次数即为总长度减去两倍 LCS 长度。

更直接的动态规划思路：定义 dp[i][j] 为使 word1[0..i-1] 和 word2[0..j-1] 相同所需的最小删除次数。初始化时注意边界条件——将字符串删为空串需要删除其全部字符。

class Solution {
public:
    int minDistance(string strA, string strB) {
        int m = strA.size();
        int n = strB.size();
        vector<vector<int>> f(m + 1, vector<int>(n + 1, 0));
        
        for (int i = 0; i <= m; ++i) f[i][0] = i;
        for (int j = 0; j <= n; ++j) f[0][j] = j;
        
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (strA[i - 1] == strB[j - 1]) {
                    f[i][j] = f[i - 1][j - 1];
                } else {
                    f[i][j] = min(f[i - 1][j], f[i][j - 1]) + 1;
                }
            }
        }
        return f[m][n];
    }
};

72. 编辑距离

编辑距离是经典的动态规划问题，允许插入、删除、替换三种操作。状态定义与上一题类似，但转移更为复杂：当字符匹配时无需操作；不匹配时，需考虑替换（f[i-1][j-1] + 1）、删除（f[i-1][j] + 1）、插入（f[i][j-1] + 1）三种情况的最小值。

实现时需特别注意下标处理，字符串索引与 DP 表索引存在一位偏移。

class Solution {
public:
    int minDistance(string first, string second) {
        int rows = first.length();
        int cols = second.length();
        vector<vector<int>> opt(rows + 1, vector<int>(cols + 1, 0));
        
        for (int i = 0; i <= rows; ++i) opt[i][0] = i;
        for (int j = 0; j <= cols; ++j) opt[0][j] = j;
        
        for (int i = 1; i <= rows; ++i) {
            for (int j = 1; j <= cols; ++j) {
                if (first[i - 1] == second[j - 1]) {
                    opt[i][j] = opt[i - 1][j - 1];
                } else {
                    int replaceCost = opt[i - 1][j - 1];
                    int deleteCost = opt[i - 1][j];
                    int insertCost = opt[i][j - 1];
                    opt[i][j] = 1 + min({replaceCost, deleteCost, insertCost});
                }
            }
        }
        return opt[rows][cols];
    }
};

392. 判断子序列

判断 s 是否为 t 的子序列，可采用双指针法，时间复杂度 O(n)。若需频繁查询不同 s，可预处理 t 中每个位置之后各字符的下个出现位置，实现 O(m) 的查询效率。

class Solution {
public:
    bool isSubsequence(string sub, string target) {
        int p = 0, q = 0;
        int lenSub = sub.size();
        int lenTgt = target.size();
        
        while (p < lenSub && q < lenTgt) {
            if (sub[p] == target[q]) {
                ++p;
            }
            ++q;
        }
        return p == lenSub;
    }
};