LeetCode刷题day26——动态规划

647. 回文子串

(https://leetcode.cn/problems/palindromic-substrings/)

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

示例 1：

输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"

示例 2：

输入：s = "aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

提示：

• 1 <= s.length <= 1000
• s 由小写英文字母组成

分析：

这题有点难，不会写，但是还是要写对吧。

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

• 动态规划方程：

  if s[i]==s[j]:
  1. 如果i==j||j-i==1:显然是回文串，eg:"a","aa"
  2. 查看前一个状态是不是回文串，if dp[i+1][j-1]==true ：显然也是回文串
  

  

观察动态规划方程，发现左下角是上一个状态，所以初始化要从i = len - 1开始，而且j = i，这是从它自己作为串开始的。

class Solution {
public:
    int countSubstrings(string s) {
        int len = s.length();
        vector<vector<bool>> dp(len, vector<bool>(len, false));
        int result = 0;
        for (int i = len - 1; i >= 0; i--) {
            for (int j = i; j < len; 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;
    }
};

5. 最长回文子串

(https://leetcode.cn/problems/longest-palindromic-substring/)

给你一个字符串 s，找到 s 中最长的 回文子串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

提示：

• 1 <= s.length <= 1000
• s 仅由数字和英文字母组成

//只需要记录最长的即可，在上一题做个小改动
class Solution {
public:
    string longestPalindrome(string s) {
        int len = s.length();
        vector<vector<bool>> dp(len, vector<bool>(len, false));
        int result = 0;
        int start = 0, end = 0;
        for (int i = len - 1; i >= 0; i--) {
            for (int j = i; j <len; j++) {
                if (s[i] == s[j]) {
                    if (j - i <= 1)
                        dp[i][j] = true;
                    else if (dp[i + 1][j - 1])
                        dp[i][j] = true;
                }
                if (dp[i][j]) {
                    if (result < j - i) {
                        start = i;
                        end = j;
                        result = j - i;
                    }
                }
                //cout<<start<<" "<<end<<endl;
            }
        }

       
        return s.substr(start, end - start + 1);
    }
};

516. 最长回文子序列

[(https://leetcode.cn/problems/longest-palindromic-subsequence/)

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

示例 1：

输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。

示例 2：

输入：s = "cbbd"
输出：2
解释：一个可能的最长回文子序列为 "bb" 。

提示：

• 1 <= s.length <= 1000
• s 仅由小写英文字母组成

问题的核心是给定一个字符串 s，求出其中的最长回文子序列的长度。与回文子串不同，回文子序列不要求字符在原字符串中的位置是连续的，只要求字符的相对顺序保持不变。

动态规划思路：

1. 定义状态： 我们定义 dp[i][j] 为子串 s[i..j] 的最长回文子序列的长度。
2. 初始化：
   • 对于每个单个字符的子串，最长回文子序列的长度为 1。即 dp[i][i] = 1。
3. 状态转移：
   • 如果 s[i] == s[j]，那么 s[i..j] 可以扩展成 s[i+1..j-1] 的回文子序列，长度加 2：
     dp[i][j] = dp[i + 1][j - 1] + 2
   • 如果 s[i] != s[j]，那么最长回文子序列要么去掉 s[i]，要么去掉 s[j]，所以：
     dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
4. 最终结果：
   • 我们需要的答案是 dp[0][len-1]，即整个字符串 s[0..len-1] 的最长回文子序列长度。

class Solution {
public:
    int longestPalindromeSubseq(string s) {
       int len = s.length();
        vector<vector<int>> dp(len, vector<int>(len, 0));
        for (int i = 0; i < len; i++) {
            dp[i][i] = 1;
        }
        int result = 1;
        for (int i = len - 1; i >= 0; i--) {
            for (int j = i+1; j < len; 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]);
                }
                result = max(result, dp[i][j]);
            }
        }
        return result;
    }
};

72. 编辑距离

(https://leetcode.cn/problems/edit-distance/)

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

• 插入一个字符
• 删除一个字符
• 替换一个字符

示例 1：

输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

示例 2：

输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

提示：

• 0 <= word1.length, word2.length <= 500
• word1 和 word2 由小写英文字母组成

分析：

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

• 状态转移：

  当 word1[i - 1] == word2[j - 1] 时，无需编辑，dp[i][j] = dp[i - 1][j - 1]，因为当前字符相同，编辑距离与前一个子问题相同。

  如果 word1[i - 1] != word2[j - 1]，则需要进行编辑，可能有三种操作：

  1. 删除 word1[i - 1]，即 dp[i][j] = dp[i - 1][j] + 1。就是查看上一个没有word[i-1]的状态的dp.
  2. 删除 word2[j - 1]，即 dp[i][j] = dp[i][j - 1] + 1。
  3. 替换 word1[i - 1] 为 word2[j - 1]，即 dp[i][j] = dp[i - 1][j - 1] + 1。

  最终，dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1，表示选择三种操作中所需的最小操作数。(上面没有添加的原因是，删除的效果和添加一样)

class Solution {
public:
    int minDistance(string word1, string word2) {
        int len1 = word1.length(), len2 = word2.length();
        vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));
        for(int i = 0; i <= len1; i++) {
            dp[i][0] = i;
        }
        for(int i = 0; i <= len2; i++) {
            dp[0][i] = i;
        }
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (word1[i - 1] == word2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                   /*{} 是 C++ 中用来创建一个临时容器的方式，min({a, b, c}) 就是对这个容器中的元素求最小值，它允许你同时比较多个值并返回最小值。在你的代码中，这种方式使得代码更加简洁，避免了多次调用 min。*/
                    dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;
                }
            }
        }
        return dp[len1][len2];
    }
};

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

(https://leetcode.cn/problems/delete-operation-for-two-strings/)

给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步数。

每步 可以删除任意一个字符串中的一个字符。

示例 1：

输入: word1 = "sea", word2 = "eat"
输出: 2
解释: 第一步将 "sea" 变为 "ea" ，第二步将 "eat "变为 "ea"

示例 2:

输入：word1 = "leetcode", word2 = "etco"
输出：4

提示：

• 1 <= word1.length, word2.length <= 500
• word1 和 word2 只包含小写英文字母

分析：

这题我用LCS做的，求出最长公共子序列，然后每一个串都要变成这样，最后计算一下差值。

class Solution {
public:
    int minDistance(string word1, string word2) {
        int len1 = word1.length(), len2 = word2.length();
        vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (word1[i - 1] == word2[j - 1]) {
                    dp[i][j] = 1 + dp[i - 1][j - 1];
                } else
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        //cout<<dp[len1][len2]<<endl;
        return len1+len2-2*dp[len1][len2];
    }
};

392. 判断子序列

https://leetcode.cn/problems/is-subsequence/

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

进阶：

如果有大量输入的 S，称作 S1, S2, … , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

致谢：

特别感谢 @pbrother 添加此问题并且创建所有测试用例。

示例 1：

输入：s = "abc", t = "ahbgdc"
输出：true

示例 2：

输入：s = "axc", t = "ahbgdc"
输出：false

提示：

• 0 <= s.length <= 100
• 0 <= t.length <= 10^4
• 两个字符串都只由小写字符组成。

分析：

这题也是用LCS做的，看一下最长公共子序列的长度，是否和s的长度相同。

只是需要提前判断一下给定字符串 **s** 和 **t** ，判断 **s** 是否为 **t** 的子序列。空串的情况。

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int len1=s.length(), len2=t.length();
        //判断空串的情况
        if(len1==0)
        return true;
        if(len2==0)
        return false;
        vector<vector<int>> dp(len1+1, vector<int>(len2+1, 0));
        //还是用LCS做的
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (s[i-1] == t[j-1]) {
                    dp[i][j] = 1 + dp[i-1][j-1];
                }
                else
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
        if(dp[len1][len2]==len1)
            return true;
        else
            return false;
    }
};