1. Toy模板网首页
  2. > Toy博客

力扣动态规划专题（六）编辑距离与回文问题 步骤及C++实现

9月前 作者：虚假自律就会真自律！ 分类：Toy博客 阅读(32) 违法举报

这篇具有很好参考价值的文章主要介绍了力扣动态规划专题（六）编辑距离与回文问题 步骤及C++实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

力扣动态规划专题（六）编辑距离与回文问题 步骤及C++实现

392. 判断子序列

力扣动态规划专题（六）编辑距离与回文问题 步骤及C++实现

动态规划

步骤

  1. 确定dp数组以及下标的含义
    dp[i][j] 表示以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度。判断s是否为t的子序列。即t的长度是大于等于s的

  2. 确定递推公式
    和题1143一样，不同的是只有t可以删除元素，1143题两个字符串都可以删除元素

  • t中找到一个在s中有的字符，if (s[i - 1] == t[j - 1])，相当于t要删除元素，继续匹配，dp[i][j] = dp[i - 1][j - 1] + 1;
  • t中没有找到s中有的字符，if (s[i - 1] != t[j - 1])，相当于t要删除元素，如果删除当前元素t[j - 1]，那么dp[i][j]的数值就是看s[i - 1]与 t[j - 2]的比较结果了，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]都要初始化的，dp[i][0] 表示以下标i-1为结尾的字符串与空字符串的相同子序列长度，所以dp[i][0]=0，同理dp[0][j]=0。
    和题718一样，如果dp[i][j]是以下标i为结尾的字符串s和以下标j为结尾的字符串t，需要对第一行和第一列单独初始化，dp[i][0]=1，dp[0][j]=1

  2. 确定遍历顺序
    dp[i][j]依赖于dp[i - 1][j - 1] 和 dp[i][j - 1]，遍历顺序从上到下，从左到右
    力扣动态规划专题（六）编辑距离与回文问题 步骤及C++实现

  3. 举例推导dp数组
    以示例一为例，输入：s = “abc”, t = “ahbgdc”，如果过dp[s.size()][t.size()] 与 字符串s的长度相同说明：s与t的最长相同子序列就是s，s 就是 t 的子序列
    力扣动态规划专题（六）编辑距离与回文问题 步骤及C++实现

  4. C++实现
    时间复杂度mn，时间复杂度mn

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;
    }
};

双指针

两个指针i和j分别指向s和t的起始位置，如果s[i]==t[j]，双指针同时后移；如果不相等，i不移动，j后移。如果i到达s的末尾，说明s是t的子序列。
时间复杂度n，空间复杂度1

class Solution {
public:
    bool isSubsequence(string s, string t) {
        //双指针
        int i=0, j=0;
        for(; i<s.size() && j<t.size(); j++)
        {
            if(s[i] == t[j]) i++;
        }
        //if(i == s.size()) return true;
        return i == s.size();
    }
};

115.不同的子序列

力扣动态规划专题（六）编辑距离与回文问题 步骤及C++实现

步骤

  1. 确定dp数组以及下标的含义
    dp[i][j]：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数

  2. 确定递推公式
    1）如果s[i - 1] = t[j - 1]，dp[i][j]可以有两部分组成。

  • 用s[i - 1]来匹配，个数为dp[i - 1][j - 1]，即不需要考虑当前s子串和t子串的最后一位字母，只需要 dp[i-1][j-1]
  • 不用s[i - 1]来匹配，个数为dp[i - 1][j]
  • 例如： s：bagg 和 t：bag ，s[3] 和 t[2]是相同的。不用s[3]来匹配的话就是用s[0]s[1]s[2]组成的bag，用s[3]来匹配的话就是s[0]s[1]s[3]组成的bag。所以，if(s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];

2）如果s[i - 1] 与 t[j - 1]不相等时，dp[i][j]只有一部分组成

  • 不用s[i - 1]来匹配，相当于模拟在s中删除这个元素，if(s[i - 1] != t[j - 1]) dp[i][j] = dp[i - 1][j];
  • 注意题目求的是 s 中有多少个 t，而不是t中有多少个s，所以只考虑 s中删除元素的情况，故不用s[i - 1]来匹配 的情况。
  1. dp数组如何初始化
  • dp[i][0]：以i-1为结尾的s出现空字符串的个数，s删除所有元素出现空字符串的个数只能是1，dp[i][0]=1
  • dp[0][j]：空字符串s出现以j-1为结尾的字符串t的个数，s子序列不可能组成t，dp[0][j]=0，
  • dp[0][0]：空字符串s，可以删除0个元素，变成空字符串t，dp[0][0]=1

  1. 确定遍历顺序
    dp[i][j]依赖于dp[i - 1][j - 1] 和 dp[i][j - 1]，遍历顺序从上到下，从左到右
    力扣动态规划专题（六）编辑距离与回文问题 步骤及C++实现

  2. 举例推导dp数组
    输入，s：“baegg”，t：“bag”
    力扣动态规划专题（六）编辑距离与回文问题 步骤及C++实现

  3. C++实现文章来源地址https://www.toymoban.com/news/detail-500722.html

class Solution {
public:
    int numDistinct(string s, string t) {
        //三种情况初始化 dp[0][0] dp[i][0] dp[0][j]
        //s匹配t  dp[i][j] 以i-1为结尾的s子序列中出现以j-1为结尾的t的个数

        vector<vector<uint64_t>> dp(s.size()+1, vector<uint64_t>(t.size()+1));//不能用int
        for(int i=0; i<s.size(); i++) dp[i][0] = 1;//初始化 dp[0][0] dp[i][0]
        for(int j=1; j<t.size(); j++) dp[0][j] = 0;//初始化dp[0][j]
        //dp
        for(int i=1; i<=s.size(); i++)
        {
            for(int j=1; j<=t.size(); j++)
            {
                //s匹配t s:bagg t:bag s[0]s[1]s[2]或者s[0]s[1]s[3] 组成t
                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()];
    }
};

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

力扣动态规划专题（六）编辑距离与回文问题 步骤及C++实现

方法一

和题115思路一致，两个字符串都可以删除操作。

步骤

  1. 确定dp数组以及下标的含义
    dp[i][j]：以i-1为结尾的字符串word1，和以j-1位结尾的字符串word2，达到相等需要删除元素的最少次数。

  2. 确定递推公式
    1）if(word1[i - 1] == word2[j - 1])，dp[i][j] = dp[i - 1][j - 1];

2）if(word1[i - 1] != word2[j - 1])，dp[i][j]有三种情况

  • 情况一：删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] = min({dp[i - 1][j - 1] + 2, dp[i - 1][j] + 1, dp[i][j - 1] + 1});。
  • dp[i][j-1]是以i-1为结尾的字符串word1和以j-2位结尾的字符串，不考虑word2[j - 1]，那么在dp[i][j-1]基础上再删除 word1[i - 1]，相当于同时删除word1[i - 1]和word2[j - 1]，即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要删除i个元素才能和word2相等，因此dp[i][0] = i。同理，dp[0][j] = j

  2. 确定遍历顺序
    dp[i][j]依赖于dp[i - 1][j - 1] 和 dp[i][j - 1]，遍历顺序从上到下，从左到右
    力扣动态规划专题（六）编辑距离与回文问题 步骤及C++实现

  3. 举例推导dp数组
    输入，word1:“sea”，word2:“eat”
    力扣动态规划专题（六）编辑距离与回文问题 步骤及C++实现

  4. C++实现

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;
        //dp数组更新
        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()];
    }
};

方法二

和题1143.最长公共子序列一样，只要求出两个字符串的最长公共子序列长度即可。除了最长公共子序列，其他字符都是必须删除的，用两个字符串的总长度减去两个最长公共子序列的长度就是删除的最少步数。

class Solution {
public:
    int minDistance(string word1, string word2) {
        //方法2
        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;
    }
};

72. 编辑距离

力扣动态规划专题（六）编辑距离与回文问题 步骤及C++实现

步骤

  1. 确定dp数组以及下标的含义
    dp[i][j] 表示以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2，最近编辑距离

  2. 确定递推公式
    1）if(word1[i - 1] == word2[j - 1])，字符相同，不操作，dp[i][j] = dp[i - 1][j - 1];

2）if(word1[i - 1] != word2[j - 1])，字符不同，插入、删除、替换三种操作

  • 操作一：word1删除一个元素，相当于是以下标i - 2为结尾的word1 与 j-1为结尾的word2的最近编辑距离dp[i - 1][j] 加一个操作，最少操作次数为：dp[i][j] = dp[i - 1][j] + 1;
  • 操作二：word1删除一个元素，同理dp[i][j - 1]加一个操作，最少操作次数为：dp[i][j] = dp[i][j - 1] + 1;
  • 操作三：替换元素，word1替换word1[i - 1]，使其与word2[j - 1]相同。此时相当于字符相同时不操作，那么在此基础上再加一次替换操作即可，dp[i][j] = dp[i - 1][j - 1] + 1;
  • 添加元素相当于删除元素，例如word1 = “ad” ，word2 = “a”，word1删除元素’d’ 和 word2添加一个元素’d’，变成word1=“a”, word2=“ad”， 最终的操作数是一样的。
    因此，当 if (word1[i - 1] != word2[j - 1]) 时，最小的操作数为：dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;

  1. dp数组如何初始化
    dp[i][0]表示以下标i-1为结尾的字符串word1和空字符串word2的最近编辑距离。相当于把word1里的元素全部删除，dp[i][0] = i;。同理，dp[0][j] = j;

  2. 确定遍历顺序

  • dp[i][j] = dp[i - 1][j - 1]
  • dp[i][j] = dp[i - 1][j - 1] + 1
  • dp[i][j] = dp[i][j - 1] + 1
  • dp[i][j] = dp[i - 1][j] + 1
    从递推公式来看，有四个推导公式，也就是有三个方向可以推出dp[i][j]，所以要从前向后，从上到下来遍历
    力扣动态规划专题（六）编辑距离与回文问题 步骤及C++实现

  1. 举例推导dp数组
    以示例1为例，输入：word1 = “horse”, word2 = “ros”
    力扣动态规划专题（六）编辑距离与回文问题 步骤及C++实现

  2. C++实现

class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word1.size()+1, vector<int>(word2.size()+1, 0));
        //初始化 dp[i][0] dp[0][j]
        for(int i=0; i<=word1.size(); i++) dp[i][0] = i;
        for(int j=0; j<=word2.size(); j++) dp[0][j] = j;
        //dp数组更新
        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];//字符相同不操作
                //字符不相同 替换dp[i - 1][j - 1] + 1
                //或者 删word1 dp[i-1][j]+1
                //或者 删word2 dp[i][j-1]+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. 回文子串

力扣动态规划专题（六）编辑距离与回文问题 步骤及C++实现

动态规划

时间、空间复杂度：O(n^2)

字符串s=“cbabc”， 如果s[1]、s[2]、s[3]组成的字符串是回文，那么进一步要判断s[0]与s[4]是否相等，如果相等，s就是回文字符串。

步骤

  1. 确定dp数组以及下标的含义
    布尔类型的dp[i][j]：表示左闭右闭区间范围[i,j]的子串是否为回文子串，如果是，dp[i][j]为true，否则为false。

  2. 确定递推公式
    1）s[i]与s[j]不相等，dp[i][j]一定是false。
    2）s[i]与s[j]相等时，有如下三种情况

  • 情况一：下标i 与 j相同，同一个字符，例如a，回文子串
  • 情况二：下标i 与 j相差为1，例如aa，回文子串
  • 情况三：下标i 与 j相差大于1时，例如cabac，此时s[i]与s[j]都是“c”，再看[i, j]区间是不是回文子串，也就是看aba是否为回文。aba的区间[i+1, j-1]是否为回文，就看dp[i + 1][j - 1]是否为true。

  1. dp数组如何初始化
    dp[i][j]初始化为false

  2. 确定遍历顺序
    情况三中dp[i][j]依赖于dp[i + 1][j - 1]，dp[i + 1][j - 1] 在 dp[i][j]的左下角，所以从下到上，从左到右遍历
    力扣动态规划专题（六）编辑距离与回文问题 步骤及C++实现

  3. 举例推导dp数组
    输入：“aaa”，j一定是大于等于i的，那么在填充dp[i][j]的时候一定是只填充右上半部分
    力扣动态规划专题（六）编辑距离与回文问题 步骤及C++实现

  4. C++实现

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)//情况1 2
                    {
                        result++;
                        dp[i][j] = true;
                    }
                    else if(dp[i+1][j-1])//情况3
                    {
                        result++;
                        dp[i][j] = true;
                    }
                }
            }
        }
        return result;
    }
};

优化

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] && (j - i <= 1 || dp[i+1][j-1]))
                {
                        result++;
                        dp[i][j] = true; 
                }
            }
        }
        return result;
    }
};

双指针

时间复杂度：O(n^2)，空间复杂度：O(1)

class Solution {
public:
    int countSubstrings(string s) {
        //双指针
        int result = 0;
        for(int center=0; center<2 * s.size() - 1; center++)
        {
            int left = center / 2;
            int right = left + center % 2;
            while(left>=0 && right<s.size() && s[left]==s[right])
            {
                left--;
                right++;
                result++;
            }
        }
        return result;
    }
};

516.最长回文子序列

力扣动态规划专题（六）编辑距离与回文问题 步骤及C++实现

回文子串是要连续的，回文子序列不是连续的

步骤

  1. 确定dp数组以及下标的含义
    dp[i][j]：字符串s在[i, j]范围内最长的回文子序列的长度

  2. 确定递推公式

  • 如果s[i]与s[j]相同，那么dp[i][j] = dp[i + 1][j - 1] + 2;
  • 如果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]);

  1. dp数组如何初始化
    从递推公式：dp[i][j] = dp[i + 1][j - 1] + 2; 可以看出，递推公式是计算不到 i == j的情况，需要手动初始化。当i与j相同时，dp[i][j]=1，一个字符的回文子序列长度就是1。其他情况dp[i][j]初始为0。

  2. 确定遍历顺序
    dp[i][j] 依赖于 dp[i + 1][j - 1] ，dp[i + 1][j] 和 dp[i][j - 1]，从下到上，从左向右遍历。
    力扣动态规划专题（六）编辑距离与回文问题 步骤及C++实现

  3. 举例推导dp数组
    输入s:“cbbd”
    力扣动态规划专题（六）编辑距离与回文问题 步骤及C++实现

  4. C++实现

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];
    }
};

到了这里，关于力扣动态规划专题（六）编辑距离与回文问题 步骤及C++实现的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 力扣72. 编辑距离（动态规划）

    力扣72. 编辑距离（动态规划）

    Problem: 72. 编辑距离 由于易得将字符串word1向word2转换和word2向word1转换是等效的，则我们假定统一为word1向word2转换！！！ 1.确定状态：我们假设现在有下标i，j分别指向字符串word1和word2 尾部的字符 ，dp(i,j)表示当前的操作则： 1.1. dp(i- 1, j) + 1;表示 删除 ，直接把word1[i]的这个字

    2024年02月21日
    浏览(45)
  • 编辑距离的动态规划

    编辑距离的动态规划

    编辑距离，也称 Levenshtein 距离，指两个字符串之间互相转换的最少修改次数，通常用于在信息检索和自然语言处理中度量两个序列的相似度。 Question 输入两个字符串 (s) 和 (t) ，返回将 (s) 转换为 (t) 所需的最少编辑步数。 你可以在一个字符串中进行三种编辑操作

    2024年04月08日
    浏览(35)
  • 【算法一则】编辑距离 【动态规划】

    【算法一则】编辑距离 【动态规划】

    给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作： 插入一个字符 删除一个字符 替换一个字符 这个问题可以使用动态规划来解决。我们可以定义一个二维数组dp，其中dp[i][j]表示将word1的前i个字符转换成word

    2024年04月24日
    浏览(36)
  • 编辑距离（动态规划）

    编辑距离（动态规划）

    题目描述 给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作： 插入一个字符 删除一个字符 替换一个字符 编辑距离：是指两个字符串之间，由一个转成另一个所需的最少编辑操作次数。 问题：word1到word2的

    2023年04月08日
    浏览(34)
  • 【Leetcode72】编辑距离（动态规划）

    【Leetcode72】编辑距离（动态规划）

    （1）确定状态 dp[i][j] 表示word1中前 i 个单词，变换到word2中前 j 个字符，最少需要的动作次数。 （2）状态转移方程 编辑距离可以通过以下三种操作进行计算：插入一个字符、删除一个字符、替换一个字符。因此，可以使用以下状态转移方程： 如果 A[i] == B[j] ，那么 dp[i][j]

    2024年02月12日
    浏览(42)
  • 【算法】动态规划算法求（编辑距离）

    【算法】动态规划算法求（编辑距离）

    目录 编辑距离： 举例： 代码如下 调试： 核心代码： 画图演示上述代码：    是一种计算两个自符串之间差异程度的方法，它通过比较 两个字符串之间的插入，删除和 替换操作的数量 ，来确定他们之间的距离。 现有两个字符串 字符串s1：”CTGA\\\" 字符串s2:  \\\"ACGCTA\\\" 求s1和

    2024年02月12日
    浏览(40)

  • 动态规划Day16(编辑距离，删除元素待写完)

    目录 583. 两个字符串的删除操作 看到题目的第一想法                看到代码随想录之后的想法 自己实现过程中遇到的困难(看代码) 72. 编辑距离 看到题目的第一想法                看到代码随想录之后的想法 自己实现过程中遇到的困难(看代码) 力扣题目链接(opens new

    2024年01月24日
    浏览(48)
  • 【LeetCode:72. 编辑距离 | 暴力递归=＞记忆化搜索=＞动态规划 】

    【LeetCode:72. 编辑距离 | 暴力递归=＞记忆化搜索=＞动态规划 】

    🚀 算法题 🚀 🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀 🌲 越难的东西,越要努力坚持，因为它具有很高的价值，算法就是这样✨ 🌲 作者简介：硕风和炜，CSDN-Java领域新星创作者🏆，保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文

    2024年02月06日
    浏览(51)

  • 动态规划16 | ● 583. 两个字符串的删除操作 ● *72. 编辑距离

    https://programmercarl.com/0583.%E4%B8%A4%E4%B8%AA%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%9A%84%E5%88%A0%E9%99%A4%E6%93%8D%E4%BD%9C.html 考点 子序列问题 我的思路 dp[i][j]的含义是，当两个字符串分别取前i和j个元素时，对应的最少相等删除步数是多少 递推公式为，如果两个字符串第i和j个元素恰好相等，则dp值应

    2024年04月22日
    浏览(47)
  • 动态规划经典题：编辑距离(hard) 详解，看了还不会你来砍我

    动态规划经典题：编辑距离(hard) 详解，看了还不会你来砍我

    🧸🧸🧸 各位大佬大家好，我是猪皮兄弟 🧸🧸🧸 为了更好的理解，我们从易到难的来解决编辑距离的问题 Leetcode最长公共子序列 一般的，我们在做序列DP问题的时候，遇到两个字符串都会用一个二维数组来进行DP，最长公共子序列简称LCS(longest common subsequence) 对于本题 状

    2024年01月22日
    浏览(36)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包