常见字符串动规解法总结

总结

• 根据连续还是非连续定义dp数组，也就是注意区分子序列或子串；

• dp[i]含义有以nums[i]结尾的【j，i】区间，或【0，i】区间范围内；

• 遍历顺序根据递推公式确定，可能有：

• • 一维dp[i]一般是从前往后遍历；
  • 二维dp[i][j]分情况：
• • • 如果是一个字符串，例如回文串，从下往上遍历；
    • 如果是两个字符串，一般是从上往下、从左往右遍历；

• 注意初始化；

最长公共子序列

class Solution {
public:
    int longestCommonSubsequence(string s1, string s2) {
        int m = s1.size();
        int n = s2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        // dp[i][j]表示 s1中0~i-1 与 s2中0~j-1 最长相同子序列的长度
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (s1[i - 1] == s2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
                }
            }
        }
        return dp[m][n];
    }
};

最长相同连续子数组

class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size();
        int n = nums2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        // dp[i][j]表示 nums1中以i-1结尾的 与 nums2中以j-1结尾的 最长相同子数组的长度

        int ans = 0;
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } 
                ans = max(ans, dp[i][j]);
            }
        }
        return ans;
    }
};

不同子序列个数

class Solution {
public:
    int numDistinct(string s, string t) {
        int m = s.size();
        int n = t.size();
        if (m < n) return 0;
        if (n == 0) return 1;

        // 令A为s中以i-1为结尾的子串，B为t中以j-1为结尾的子串；
        // dp[i][j] 表示A的子序列中B的个数
        vector<vector<uint64_t>> dp(m + 1, vector<uint64_t>(n + 1, 0));

        for (int j = 1; j <= n; ++j) dp[0][j] = 0;
        for (int i = 0; i <= m; ++i) dp[i][0] = 1;

        // 递推公式中[j]其实对应t这个不变的串，只有某字符相等时用到[j-1]
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                dp[i][j] = dp[i - 1][j];
                if (s[i - 1] == t[j - 1]) {
                    dp[i][j] += dp[i - 1][j - 1];
                }
            }
        }

        return dp[m][n];
    }
};

编辑距离

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size();
        int n = word2.size();

        // 令A为s中以i-1为结尾的子串，B为t中以j-1为结尾的子串；
        // dp[i][j] 表示使AB相同的最小操作步数
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

        for (int j = 1; j <= n; ++j) dp[0][j] = j;
        for (int i = 0; i <= m; ++i) dp[i][0] = i;

        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (word1[i - 1] == word2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    //                  word1删        word2删        替换
                    dp[i][j] = 1 + min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]});
                }
            }
        }

        return dp[m][n];
    }
};