• leetCode 583.两个字符串的删除操作 动态规划 + 优化空间复杂度（二维dp、一维dp）

    583. 两个字符串的删除操作 - 力扣（LeetCode）

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

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

    示例 1：

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

    示例  2:

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

     一、递归搜索 + 保存计算结果 = 记忆化搜索

     

    • 二维memo数组 存储计算过的子问题的结果 
    1. class Solution {
    2. public:
    3.     // 递归搜索 + 保存计算结果 = 记忆化搜索
    4.     // 二维memo数组 存储过的子问题的结果
    5.     int minDistance(string s, string t) {
    6.         int m = s.size(),n = t.size(),memo[m][n]; // 二维memo数组 存储计算过的子问题的结果;
    7.         memset(memo,-1,sizeof(memo));// -1 表示没有访问过
    8.         function<int(int,int)> dfs = [&](int i,int j) -> int {
    9.             if(i<0) //base case 当i指针越界，此时
    10.                 return j+1;
    11.             if(j<0) //base case
    12.                 return i+1;
    13.             if (memo[i][j] != -1) // memo中有当前遇到的子问题的解，直接拿来返回
    14.                 return memo[i][j];
    15.             if (s[i] == t[j]) {  
    16. 			    memo[i][j] = dfs(i-1, j-1);
    17. 		    } else {
    18. 			    // memo[i][j] = min(min(dfs(i-1, j)+1,dfs(i, j-1)+1),dfs(i-1, j-1)+2);
    19.                 // memo[i][j] = min(dfs(i-1, j)+1,dfs(i, j-1)+1);
    20.                 memo[i][j] = min(dfs(i-1, j),dfs(i, j-1))+1;
    21. 		    }
    22.             return memo[i][j];
    23.         };
    24.         return dfs(m-1,n-1);
    25.     }
    26. }

    二、动态规划 与 递归 的区别 

    • 递归公式 
    1. if (s[i] == t[j]) {  
    2.     memo[i][j] = dfs(i-1, j-1);
    3. } else {
    4.     // memo[i][j] = min(min(dfs(i-1, j)+1,dfs(i, j-1)+1),dfs(i-1, j-1)+2);
    5.     // memo[i][j] = min(dfs(i-1, j)+1,dfs(i, j-1)+1);
    6.     memo[i][j] = min(dfs(i-1, j),dfs(i, j-1))+1;
    7. }

    递归是自上而下调用，子问题自下而上被解决，最后解决了整个问题，而dp是从base case 出发，通过在dp数组记录中间结果，自下而上地顺序地解决子问题

    • dp解法

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

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

    2.确定递推公式

    1. if (word1[i - 1] == word2[j - 1]) {
    2.     dp[i][j] = dp[i - 1][j - 1];
    3. } else {
    4.     dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
    5. }

    3.dp数组初始化

    从递推式可看出，dp[i][0] 和 dp[0][j] 是一定要初始化的

    • dp[i][0]:word2为字符串，以 i-1 为结尾的字符串 word1 需要删除 i 个元素才能变成空串，和word2相同
    • dp[0][j]:word1为字符串，以 j-1 为结尾的字符串 word2 需要删除 j 个元素才能变成空串，和word1相同
    • dp[0][0]=0,因为两个空字符串相同，删除操作为0
    1. for(int i=1;i<=m;++i) dp[i][0] = i;
    2. for(int j=1;j<=n;++j) dp[0][j] = j;

    4.确定遍历顺序

    从递推公式 dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1;  和dp[i][j] = dp[i - 1][j - 1]可以看出dp[i][j]都是根据左上方、正上方、正左方推出来的。所以遍历的时候一定是从上到下，从左到右，这样保证dp[i][j]可以根据之前计算出来的数值进行计算。

    5.举例推导dp数组

    嘻嘻，假设我们上文这些全都不会，那我们还想要知道递推式，还想用动态规划来解决此问题，那该怎么做呢？有请各位友友继续耐心往下看~

    这个表格该怎么填呢，我们先按照左边的图标注好每个格子上面的字符串，然后依次手动计算该删除的字数，填入格子里。比如"se" 和 "e" ，要相同所需的最小步数为1，"se" 和 "ea" ，要相同所需的最小步数为2，"se" 和 "eat" ，要相同所需的最小步数为3。以此类推，我们就可以得到下面的两张图的第一张表格。

    观察看以上力扣给的例子所推导出的表格，看我所标注的蓝色和黄色的格子，我们可以发现有如下规律：

    1. if(word1[i-1] == word2[j-1]) dp[i][j] = dp[i-1][j-1];
    2. else dp[i][j] = min(dp[i-1][j]+1,dp[i][j-1]+1);

     （1）动态规划 二维dp

    1. class Solution {
    2. public:
    3.     int minDistance(string word1, string word2) {
    4.         int m = word1.size(),n = word2.size();
    5.         vectorint>> dp(m+1,vector<int>(n+1));
    6.  
    7.         for(int i=1;i<=m;++i) dp[i][0] = i;
    8.         for(int j=1;j<=n;++j) dp[0][j] = j;
    9.  
    10.         for(int i=1;i<=m;++i) {
    11.             for(int j=1;j<=n;++j) {
    12.                 if(word1[i-1] == word2[j-1]) dp[i][j] = dp[i-1][j-1];
    13.                 // else dp[i][j] = min(min(dp[i-1][j]+1,dp[i][j-1]+1),dp[i-1][j-1]+2);
    14.                 else dp[i][j] = min(dp[i-1][j]+1,dp[i][j-1]+1);
    15.             }
    16.         }
    17.         return dp[m][n];
    18.     }
    19. };
    • 时间复杂度: O(m * n)
    • 空间复杂度: O(m * n)

    （2）动态规划 二维dp 优化空间 

    1. class Solution {
    2. public:  
    3.     // 动态规划 二维dp 优化空间
    4.     int minDistance(string word1, string word2) {
    5.         int m = word1.size(),n = word2.size();
    6.         // vector> dp(m+1,vector(n+1));
    7.         vectorint>> dp(2,vector<int>(n+1));
    8.         for(int j=1;j<=n;++j) dp[0][j] = j;
    9.         for(int i=1;i<=m;++i) {
    10.             dp[i%2][0] = i;
    11.             for(int j=1;j<=n;++j) {
    12.                 if(word1[i-1] == word2[j-1]) dp[i % 2][j] = dp[(i-1)%2][j-1];
    13.                 else dp[i%2][j] = min(dp[(i-1)%2][j]+1,dp[i%2][j-1]+1);
    14.             }
    15.         }
    16.         return dp[m%2][n];
    17.     }
    18. };
    • 时间复杂度: O(m * n)
    • 空间复杂度: O(n)

    （3）动态规划 一维dp(滚动数组) 优化空间

    1. class Solution {
    2. public:  
    3.     // 动态规划 一维dp(滚动数组) 优化空间
    4.     int minDistance(string word1, string word2) {
    5.         int m = word1.size(),n = word2.size();
    6.         vector<int> dp(n+1);
    7.  
    8.         for(int j=1;j<=n;++j) dp[j] = j;
    9.         for(int i=1;i<=m;++i) {
    10.             // pre 代表dp[i-1][0]
    11.             int pre = dp[0];
    12.             // 初始化当前层的 dp[i][0]
    13.             dp[0] = i;
    14.             for(int j=1;j<=n;++j) {
    15.                 int tmp = dp[j];
    16.                 if(word1[i-1] == word2[j-1]) dp[j] = pre;
    17.                 else dp[j] = min(dp[j]+1,dp[j-1]+1);
    18.                 pre = tmp;
    19.             }
    20.         }
    21.         return dp[n];
    22.     }
    23. };
    • 时间复杂度: O(m * n)
    • 空间复杂度: O(n)

    本题除了这种解法外，还有这种解题思路：先求出最长公共子序列,然后 word1.size() + word2.size() - 两倍的最长公共子序列

    求最长公共子序列，可以看我往期的这篇文章：leetCode 1143.最长公共子序列

    （1）二维dp 

    1. class Solution {
    2. public: 
    3.    int minDistance(string word1, string word2) {
    4.         int m = word1.size(),n = word2.size();
    5.         vectorint>> dp(m+1,vector<int>(n+1)); 
    6.         for(int i=1;i<=m;++i) {
    7.             for(int j=1;j<=n;++j) {
    8.                 if(word1[i-1] == word2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
    9.                 else dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
    10.             }
    11.         }
    12.         return m + n - 2 * dp[m][n];
    13.     }
    14. };
    • 时间复杂度: O(m * n)
    • 空间复杂度: O(m * n)

    （2）二维dp：优化空间 

    1. class Solution {
    2. public:  
    3.     // 方法二 二维dp 优化空间
    4.     int minDistance(string word1, string word2) {
    5.         int m = word1.size(),n = word2.size();
    6.         vectorint>> dp(2,vector<int>(n+1)); 
    7.         for(int i=1;i<=m;++i) {
    8.             for(int j=1;j<=n;++j) {
    9.                 if(word1[i-1] == word2[j-1]) dp[i%2][j] = dp[(i-1)%2][j-1] + 1;
    10.                 else dp[i%2][j] = max(dp[(i-1)%2][j],dp[i%2][j-1]);
    11.             }
    12.         }
    13.         return m + n - 2 * dp[m%2][n];
    14.     }
    15. };
    • 时间复杂度: O(m * n)
    • 空间复杂度: O(n)

    （3）一维dp：优化空间

    1. class Solution {
    2. public:
    3.     // 方法二 一维dp 优化空间
    4.     int minDistance(string word1, string word2) {
    5.         int m = word1.size(),n = word2.size();
    6.         vector<int> dp(n+1); 
    7.         for(int i=1;i<=m;++i) {
    8.             int pre = dp[0];
    9.             for(int j=1;j<=n;++j) {
    10.                 int tmp = dp[j];
    11.                 if(word1[i-1] == word2[j-1]) dp[j] = pre + 1;
    12.                 else dp[j] = max(dp[j],dp[j-1]);
    13.                 pre = tmp;
    14.             }
    15.         }
    16.         return m + n - 2 * dp[n];
    17.     }
    18. };
    • 时间复杂度: O(m * n)
    • 空间复杂度: O(n)

    参考和推荐文章、视频：

    代码随想录 (programmercarl.com)

    动态规划之子序列，还是为了编辑距离做铺垫 | LeetCode：583.两个字符串的删除操作_哔哩哔哩_bilibili

    来自代码随想录课堂的截图：

  • 相关阅读:
    蓝桥杯 第 1 场算法双周赛 第1题 三带一 c++ map 巧解 加注释
    如果编程语言是一门武功绝学
    ​力扣解法汇总795. 区间子数组个数
    个人网页设计成品DW静态网页 HTML网页设计结课作业 web课程设计网页规划与设计 Web大学生个人网页成品 web网页设计期末课程大作业
    Echarts与数据可视化
    kvm部署
    【计算机网络】高级IO初步理解
    企业为何要认定高新技术企业，都有哪些好处？
    决策树--ID3算法
    卫士之选：迅软DSE解决方案助力IT企业应对数据泄密威胁！
  • 原文地址：https://blog.csdn.net/weixin_41987016/article/details/133815470