首页 计算机科学 算法 LeetCode

# 不想交的线

题目链接🔗

直线不能相交，这就是说明在字符串 A 中找到一个与字符串 B 相同的子序列，且这个子序列不能改变相对顺序，只要相对顺序不改变，链接相同数字的直线就不会相交。

本题说是求绘制的最大连线数，其实就是求两个字符串的最长公共子序列的长度。

class Solution {
public:
    int maxUncrossedLines(vector<int>& A, vector<int>& B) {
        vector<vector<int>> dp(A.size() + 1, vector<int>(B.size() + 1, 0));
        for (int i = 1; i <= A.size(); i++) {
            for (int j = 1; j <= B.size(); j++) {
                if (A[i - 1] == B[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[A.size()][B.size()];
    }
};

# 判断子序列

题目链接🔗

编辑距离入门题。

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

dp [i][j]: 表示以下标 i-1 结尾的字符串 s 和以下标 j-1 结尾的 t，相同子序列长度为 dp [i][j]。

  1. 确定递推公式

  • if (s[i - 1] == t[j - 1])

    t 中找到了一个字符在 s 中也出现了，dp[i][j]=dp[i−1][j−1]+1dp[i][j] = dp[i - 1][j - 1] + 1

  • if (s[i - 1] != t[j - 1])

    相当于 t 要删除元素，t 如果把当前元素 t [j - 1] 删除，那么 dp [i][j] 的数值就是 看 s [i - 1] 与 t [j - 2] 的比较结果了，即：dp[i][j]=dp[i][j−1]dp[i][j] = dp[i][j - 1]

  1. dp 数组如何初始化

从递推公式可以看出 dp [i][j] 都是依赖于 dp [i - 1][j - 1] 和 dp [i][j - 1]，所以 dp [0][0] 和 dp [i][0] 是一定要初始化的。

  1. 确定遍历顺序

遍历顺序是从上到下，从左到右。

  1. 举例推导 dp 数组

Alt text

如果 dp [s.size ()][t.size ()] 与字符串 s 的长度相同说明：s 与 t 的最长相同子序列就是 s，那么 s 就是 t 的子序列。

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

# 不同的子序列

题目链接🔗

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

dp [i][j]: 以 i-1 结尾的 s 字符串中出现以 j-1 为结尾的子序列 t 个数为 dp [i][j]。

  1. 确定递推公式

  • s [i - 1] 与 t [j - 1] 相等

    • 一部分是用 s [i - 1] 来匹配，那么个数为dp[i−1][j−1]dp[i - 1][j - 1]
    • 一部分是不用 s [i - 1] 来匹配，个数为dp[i−1][j]dp[i - 1][j]

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

  • s [i - 1] 与 t [j - 1] 不相等

    dp [i][j] 只有一部分组成，不用 s [i - 1] 来匹配。dp[i][j]=dp[i−1][j]dp[i][j] = dp[i - 1][j]

  1. dp 数组如何初始化

dp[i][0] = 1，dp[0][j] = 0

  1. 确定遍历顺序

遍历是从上到下，从左到右。

  1. 举例推导 dp 数组

Alt text

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

# 两个字符串的删除操作

题目链接🔗

# 思路一

和上一题相比，两个字符串都已删除了。

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

dp [i][j]: 以 i-1 为结尾的字符串 word1，和以 j-1 为结尾的的字符串 word2，想要达到相等所需删除元素的最少次数，

  1. 确定递推公式

  • 当 word1 [i - 1] 与 word2 [j - 1] 相同的时候

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

  • 当 word1 [i - 1] 与 word2 [j - 1] 不相同的时候

    • 删 word1 [i - 1]，最少操作次数为 dp [i - 1][j] + 1

    • 删 word2 [j - 1]，最少操作次数为 dp [i][j - 1] + 1

    • 同时删 word1 [i - 1] 和 word2 [j - 1]，操作的最少次数为 dp [i - 1][j - 1] + 2

    三者取最小。因为 dp [i][j - 1] + 1 = dp [i - 1][j - 1] + 2，所以递推公式可简化为：$$dp [i][j] = min (dp [i - 1][j] + 1, dp [i][j - 1] + 1)$$

  1. dp 数组如何初始化

dp [i][0]：word2 为空字符串，以 i-1 为结尾的字符串 word1 要删除多少个元素，才能和 word2 相同呢，很明显 dp [i][0] = i。dp [0][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));
        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][j - 1] + 1);
                }
            }
        }
        return dp[word1.size()][word2.size()];
    }
};

# 思路二

求出两个字符串的最长公共子序列长度即可，那么除了最长公共子序列之外的字符都是必须删除的，最后用两个字符串的总长度减去两个最长公共子序列的长度就是删除的最少步数。

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=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] + 1;
                else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
        return word1.size()+word2.size()-dp[word1.size()][word2.size()]*2;
    }
};