algo-aha

最长公共子序列

• https://leetcode.com/problems/delete-operation-for-two-strings/
• https://leetcode.com/problems/longest-common-subsequence/
• https://leetcode.com/problems/shortest-common-supersequence/

int minDistance(string word1, string word2) {
    // 设dp[i][j]表示word1[i..]和word2[j..]的最长公共子序列长
    // word1[i]==word2[j] => dp[i][j] = 1 + dp[i+1][j+1], 
    //         !=         =>         = max(dp[i][j+1], dp[i+1][j])
    // 初始dp[n1][..]=dp[..][n2]=0，所求dp[0][0]
    const int n1 = word1.size(), n2 = word2.size();
    vector<vector<int>> dp(n1 + 1, vector<int>(n2 + 1, 0));
    for (int i = n1 - 1; i >= 0; i--) {
        for (int j = n2 - 1; j >= 0; j--) {
            if (word1[i] == word2[j]) {
                dp[i][j] = 1 + dp[i+1][j+1];
            } else {
                dp[i][j] = max(dp[i][j+1], dp[i+1][j]);
            }
        }
    }
    return n1 + n2 - 2 * dp[0][0]; // 需要删除的个数
}

最长公共子段

• https://leetcode.com/problems/maximum-length-of-repeated-subarray/

设dp[i][j]表示以A[i]开头的A[i..]、以B[j]开头的B[j..]的最长公共子段长。 若A[i]==B[j]，dp[i][j]=1+dp[i+1][j+1]；否则，dp[i][j]=0

最小编辑距离

• https://leetcode.com/problems/edit-distance/

int minDistance(string word1, string word2) {
    // 设dp[i][j]表示s1[i..]和s2[j..]的最小编辑距离
    // 若s1[i]==s2[j]，dp[i][j]=dp[i+1][j+1]；否则，
    // dp[i][j] = 1 + min{ dp[i+1][j]/*删除*/, dp[i][j+1]/*添加*/,dp[i+1][j+1]/*替换*/ }
    const int M = word1.size(), N = word2.size();
    vector<vector<int>> dp(M + 1, vector<int>(N + 1, 0));
    for (int i = M - 1; i >= 0; i--) dp[i][N] = M - i;
    for (int j = N - 1; j >= 0; j--) dp[M][j] = N - j;

    for (int i = M - 1; i >= 0; i--) {
        for (int j = N - 1; j >= 0; j--) {
            if (word1[i] == word2[j]) {
                dp[i][j] = dp[i+1][j+1];
            } else {
                dp[i][j] = 1 + min({dp[i+1][j], dp[i][j+1], dp[i+1][j+1]});
            }
        }
    }
    return dp[0][0];
}

若设dp[i][j]表示串a[0..i)和串b[0..j)的最小编辑距离，其实和前面设法一样，一个设后半段、一个设前半段，写法稍改。

等于某串的子序列个数

• https://leetcode.com/problems/distinct-subsequences/

int numDistinct(string s, string t) {
    // 设dp[i][j]表示s[i..]子序列等于t[j..]的个数 (0<=i<=M, 0<=j<=N）
    // 若s[i]==t[j]，dp[i][j] = dp[i+1][j+1]/*使用s[i]*/ + dp[i+1][j]/*不用s[i]*/
    // 若s[i]!=t[j]，dp[i][j] = dp[i+1][j]
    // 初值：dp[i][N]=1，dp[M][j<N]=0
    // 省略i这一维，i仍从右向左遍历，要让dp[j+1]是旧状态，j从左向右遍历
    const int M = s.size(), N = t.size();
    vector<int> dp(N + 1, 0); // 对应i==M
    dp[N] = 1;

    for (int i = M; i >= 0; i--) {
        for (int j = 0; j < N; j++) {
            if (s[i] == t[j]) {
                dp[j] += dp[j+1];
            }
        }
    }
    return dp[0];
}

最小ascii删除和

• https://leetcode.com/problems/minimum-ascii-delete-sum-for-two-strings/

int minimumDeleteSum(string s1, string s2) {
    // 设dp[i][j]表示s1[i..]和s2[j..]的最小ascii删除和。
    // 若s1[i]==s2[j]，dp[i][j] = dp[i+1][j+1]
    // 若s1[i]!=s2[j]，dp[i][j] = min(s1[i]+dp[i+1][j], s2[j]+dp[i][j+1])
    // 初始dp[M][N]=0，所求dp[0][0]
    const int M = s1.size(), N = s2.size();
    vector<vector<int>> dp(M + 1, vector<int>(N + 1));
    dp[M][N] = 0;
    for (int i = M - 1; i >= 0; i--) {
        dp[i][N] = s1[i] + dp[i+1][N];
    }
    for (int j = N - 1; j >= 0; j--) {
        dp[M][j] = s2[j] + dp[M][j+1];
    }

    for (int i = M - 1; i >= 0; i--) {
        for (int j = N - 1; j >= 0; j--) {
            if (s1[i] == s2[j]) {
                dp[i][j] = dp[i+1][j+1];
            } else {
                dp[i][j] = min(s1[i] + dp[i+1][j], s2[j] + dp[i][j+1]);
            }
        }
    }
    return dp[0][0];
}