首页 计算机科学 算法 LeetCode

# 编辑距离

题目链接🔗

  1. 确定 dp 数组以及下标的含义

dp [i][j]: 表示以 i-1 为结尾的字符串 word1，和以 j-1 为结尾的字符串 word2，最近的编辑距离为 dp [i][j]。

  1. 确定递推公式

  • 当 word1 [i-1] == word2 [j-1]

    • 不做任何操作：dp [i][j] = dp [i-1][j-1]

  • 当 word1 [i-1] != word [j-1]，以下三种情况取最小

    • 增：word2 删除一个元素，那么就是下标 i-1 为结尾的 word1，与 j-2 为结尾的 word2 的最近编辑距离再加上一个操作。

      dp[i][j]=dp[i][j−1]+1dp[i][j] = dp[i][j-1] + 1

    • 删：word1 删除一个元素，那么就是下标 i-2 为结尾的 word1，与 j-1 为结尾的 word2 的最近编辑距离再加上一个操作。

      dp[i][j]=dp[i−1][j]+1dp[i][j] = dp[i-1][j] + 1

    • 换：word1 替换 word1 [i - 1]，使其与 word2 [j - 1] 相同，此时不用增删加元素。

      dp[i][j]=dp[i−1][j−1]+1dp[i][j] = dp[i-1][j-1] + 1

word2 添加一个元素，相当于 word1 删除一个元素，例如 word1 = "ad" ，word2 = "a" ， word1 删除元素 'd' 和 word2 添加一个元素 'd' ，变成 word1="a" , word2="ad" ， 最终的操作数是一样。

  1. dp 数组如何初始化

dp [i][0]: 以下标 i-1 为结尾的字符串 word1，和空字符串 word2，最近编辑距离为 dp [i][0]。

那么 dp [i][0] 就应该是 i，对 word1 里的元素全部做删除操作，即：dp [i][0] = i。同理 dp [0][j] = j。

  1. 确定遍历顺序

从左到右从上到下去遍历。

  1. 举例推导 dp 数组

Alt text

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

# 回文子串

题目链接🔗

  1. 确定 dp 数组以及下标的含义

dp [i][j]：表示区间范围 [i,j] （注意是左闭右闭）的子串是否是回文子串，如果是 dp [i][j] 为 true，否则为 false。

  1. 确定递推公式
  • s[i] != s[j]: dp[i][j] = false
  • s[i] == s [j]: dp[i][j] = true
    • 情况一：下标 i 与 j 相同。同一个字符如 a，当然也是回文子串
    • 情况二：下标 i 与 j 相差为 1，例如 aa，也是回文子串
    • 情况三：下标 i 与 j 相差大于 1 的时候，例如 cabac，此时 s [i] == s [j]，查看 [i,j] 区间是不是回文子串就看 aba 是不是就可以了。那么 aba 的区间就是 [i+1, j-1]，这个区间是不是回文就看 dp [i + 1][j - 1] 是否为 true。
  1. dp 数组如何初始化

dp [i][j] 初始化为 false。初始化为 true 表示开始就全匹配上了。

  1. 确定遍历顺序

首先从递推公式中可以看出，情况三是根据 dp [i + 1][j - 1] 是否为 true，在对 dp [i][j] 进行赋值 true 的。dp [i + 1][j - 1] 在 dp [i][j] 的左下角。

如果这矩阵是从上到下，从左到右遍历，那么会用到没有计算过的 dp [i + 1][j - 1]，也就是根据不确定是不是回文的区间 [i+1,j-1]，来判断了 [i,j] 是不是回文，那结果一定是不对的。

所以一定要从下到上，从左到右遍历，这样保证 dp [i + 1][j - 1] 都是经过计算的。

  1. 举例推导 dp 数组

输入："aaa"，dp [i][j] 状态如下：

Alt text

class Solution {
public:
    int countSubstrings(string s) {
        vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));
        int result = 0;
        for (int i = s.size() - 1; i >= 0; i--) {  // 注意遍历顺序
            for (int j = i; j < s.size(); j++) {
                if (s[i] == s[j]) {
                    if (j - i <= 1) { // 情况一 和 情况二
                        result++;
                        dp[i][j] = true;
                    } else if (dp[i + 1][j - 1]) { // 情况三
                        result++;
                        dp[i][j] = true;
                    }
                }
            }
        }
        return result;
    }
};

# 最长回文子序列

题目链接🔗

本题相比上题，变化在于，子序列不是必须连续的。

  1. 确定 dp 数组以及下标的含义

dp [i][j]: 字符串 s 在 [i, j] 范围内最长的回文子序列的长度为 dp [i][j]。

  1. 确定递推公式

如果 s [i] 与 s [j] 相同，那么 dp [i][j] = dp [i + 1][j - 1] + 2

Alt text

如果 s [i] 与 s [j] 不相同，说明 s [i] 和 s [j] 的同时加入并不能增加 [i,j] 区间回文子序列的长度，那么分别加入 s [i]、s [j] 看看哪一个可以组成最长的回文子序列。

加入 s [j] 的回文子序列长度为 dp [i + 1][j]。

加入 s [i] 的回文子序列长度为 dp [i][j - 1]。

那么 dp [i][j] 一定是取最大的，即：dp [i][j] = max (dp [i + 1][j], dp [i][j - 1])

Alt text

  1. dp 数组如何初始化

首先要考虑当 i 和 j 相同的情况，从递推公式：dp [i][j] = dp [i + 1][j - 1] + 2。可以看出，递推公式是计算不到 i 和 j 相同时候的情况。

所以需要手动初始化一下，当 i 与 j 相同，那么 dp [i][j] 一定是等于 1 的，即：一个字符的回文子序列长度就是 1。

其他情况 dp [i][j] 初始为 0 就行，这样递推公式：dp [i][j] = max (dp [i + 1][j], dp [i][j - 1]); 中 dp [i][j] 才不会被初始值覆盖。

  1. 确定遍历顺序

dp [i][j] 依赖于 dp [i + 1][j - 1] ，dp [i + 1][j] 和 dp [i][j - 1]。

所以遍历 i 的时候一定要从下到上遍历，这样才能保证下一行的数据是经过计算的。

j 可以从左向右遍历。

  1. 举例推导 dp 数组

Alt text

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));
        for (int i = 0; i < s.size(); i++) dp[i][i] = 1;
        for (int i = s.size() - 1; i >= 0; i--) {
            for (int j = i + 1; j < s.size(); j++) {
                if (s[i] == s[j]) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[0][s.size() - 1];
    }
};