代码随想录算法训练营day56||72. 编辑距离||647. 回文子串 ||516.最长回文子序列

72. 编辑距离

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

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

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

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

思路：

动规五部曲：

1.dp[i][j]及其下标的定义：以下标i-1为结尾的字符串word1和以下标j-1为结尾的字符串word2的最小编辑距离是dp[i][j].

2.递推公式：

if(word[i-1]==word2[j-1])

不操作：dp[i][j]=dp[i-1][j-1]

if(word1[i-1]!=word2[j-1])

增:dp[i][j]=dp[i][j-1]+1

删:dp[i][j]=dp[i-1][j]+1

换:dp[i][j]=dp[i-1][j-1]+1

3.dp数组的初始化：dp[i][0]=i;dp[0][j]=j

4.遍历顺序：从上往下，从前往后

class Solution {
public:
    int minDistance(string word1, string word2) {
        vectorint>> 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()];
    }
};

647. 回文子串

思路：

动规五部曲：

1.dp[i][j]及其下标的定义：区间为[i,j]的s子串，是不是回文子串，如果是就赋值为true，否则赋值为false

2.递推公式：判断s[i]与s[j]是否相等，如果不相等，则不做任何处理(因为dp[i][j]的初始值为false),如果s[i]与s[j]相等则有以下三种情况：1.如果i==j那么是同一个元素,dp[i][j]=true     2.如果j-i==1那么是相邻两个元素，dp[i][j]=true.      3.如果j-i>1,则需要判断dp[i+1][j-1]是否是回文串，如果是的话才，dp[i][j]=true;

3.初始化：全部为false

4.遍历顺序：从递推公式上看遍历顺序是有讲究的，求出dp[i][j]需要dp[i+1][j-1]的值作为基础，所以遍历顺序是从下往上，从左往右

5.打印dp

class Solution {
public:
    int countSubstrings(string s) {
        vectorbool>> 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;
    }
};

516.最长回文子序列

题目描述：

给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000 。

示例 1: 输入: "bbbab" 输出: 4 一个可能的最长回文子序列为 "bbbb"。

示例 2: 输入:"cbbd" 输出: 2 一个可能的最长回文子序列为 "bb"。

思路：

动规五部曲：

1.dp[i][j]及其下标的定义：字符串s在区间[i,j]的子串，最长回文子序列数是dp[i][j].

2.递推公式：如果s[i]与s[j]相等的话，dp[i][j]=dp[i+1][j-1]+2,如果s[i]与s[j]不相等的话，dp[i][j]就有两种情况：dp[i][j]=dp[i+1][j]和dp[i][j-1]。这两种情况取最大值。(注意：一定是这两种情况，我就只考虑了一种情况，卡了很久)

3.初始化：通过递推公式可知，没有为i=j的情况，进行赋值，所以自行初始化为1,其余值都初始化为0.

4.遍历顺序：从递推公式上可以看出从下到上，从左到右。

5.打印dp

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        vectorint>> dp(s.size(),vector<int> (s.size(),1));
        for(int i=s.size()-1;i>=0;i--){
            for(int j=i;jsize();j++){
                if(s[i]==s[j]){
                    if(j-i==1){
                        dp[i][j]=2;
                    }else if(j-i>1){
                        dp[i][j]=dp[i+1][j-1]+2;
                    }
                }else{
                 dp[i][j] = dp[i + 1][j];//这一句是区分度
                }
            }
        }
        
        return dp[0][s.size()-1];
    }
};