【算法】背包问题，编辑距离，不同的子序列详细求解

小灰灰 2022-09-04 15:57 83阅读 0赞

### 动态规划 ###

*  前言
 *   *  背包问题
 *  一、编辑问题
 *  二、不同的子序列
 *  总结

--------------------

# 前言 #

## 背包问题 ##

> 本文链接前文：背包问题在下面的链接  
> [【算法】用习题教你如何使用动态规划，超详细，一看就会！！建议收藏！！][Link 1]

今天这篇来跟大家看看**编辑问题**与**不同的子序列** \--废话不多说，我们开始吧！

--------------------

# 一、编辑问题 #

[LC77 编辑距离][LC77]

> 文章概述：给定两个单词word1和word2，请计算将word1转换为word2至少需要多少步操作。  
> 你可以对一个单词执行以下3种操作：  
> a）在单词中插入一个字符  
> b）删除单词中的一个字符  
> c）替换单词中的一个字符

例子 从**word1：abc 到 word2： egh**

> 拿到这道题目大家开始想的是什么呢？  
> 首先：根据上文，我们首先要想办法弄清楚**状态的定义**是什么样的会方便后面的求解。  
> 我们先来思考一下：**状态的定义**如果设置为在word1中前i个字符转换为word2的次数。–我们可以利用这个状态再去添加字符经过一次变换得到次数吗？是不行的，因为我们没办法知道我们添加的字符是否能够构成word2  
> 所以我们这里的**状态定义**定义成word1的前i个字符经过这三种操作转换成word2的前j个字符，即：**F(i,j):word1的前i个字符于word2的前j个字符的编辑距离**

> 有了状态的定义，**状态的转换**我们又得思考一番了，**F(i,j) = ??**  
> 我们知道每个单词可以进行三种操作，**插入，删除，替换**  
> **我们逐一解释：**  
> **什么时候需要插入？** 这时F(2,1)- -**即F（i, j-1）** 即从ab -->e ,F(2,2) =F(2，1)+插入word2的第j个字符,这里的 ab已经转换为了e，我们需要添加一个g给他，即F(2,2)比起F（2，1）的编辑次数多了一次。**F（i，j）=F(i , j- 1)+1**  
> **什么时候需要删除？** F(1，2) - -**即F（i -1 ，j）** 即从a–>eg, F(1,1) =F(1,2)+删除word1的第i个字符 ，因为这时的F(1, 2)已经转换为了两个字符，所以我们这里的F（1，1）就是在F（1，2）的基础上删除一个字符。**F(i , j )=F(i-1 , j)+1**。  
> **什么时候需要替换呢？** F（i-1, j-1）这时我们的 **F（i，j）=F（i-1，j-1）+1**，但时需要考虑一种情况，**当我们的word1的第i个字符和word2的第j个字符相等时，不需要替换操作，F（i，j）还是F（i-1，j-1）**

> 分析到这里，**状态转换**F（i，j）究竟是什么很清楚了，我们每次操作一个字符，所以  
> **F（i，j） = min（插入，删除，替换）**  
> **初始化**：因为我们看到F（i，j）都可能需要 F（i-1，j）前一行，F（i-1，j-1）前一行一列，F（i，j-1）前一列的值，所以这个时候我们就多给一行一列。  
> **F（i，0）：表示给word1的前i个字符到0个字符，即进行删除操作，有多少个字符删除多少个；**  
> **F（0，j）则表示插入操作，从0字符到j字符，插入j个字符**  
> **返回结果**就是F（S.szie(),T.size()）。

class Solution { 
    public:
        /** * * @param word1 string字符串 * @param word2 string字符串 * @return int整型 */
        int minDistance(string word1, string word2) { 
            // write code here
            int row =word1.size();
            int col =word2.size();
            //vv用来保存子结果
            vector<vector<int>> vv(row+1,vector<int>(col+1,0));
            for(int i =0;i<=row;++i)
            { 
            //初始化
                vv[i][0] =i;
            }
            for(int j =0;j<=col;++j)
            { 
            //初始化
                vv[0][j] =j;
            }
            for(int i =1;i<=row;++i)
            { 
                for(int j =1;j<=col;++j)
                { 
                    //状态转换
                    //插入删除中选一个
                    vv[i][j] = min(vv[i-1][j]+1,vv[i][j-1]+1);
                    if(word1[i-1] ==word2[j-1])
                        vv[i][j] = min(vv[i-1][j-1],vv[i][j]);
                    else
                        vv[i][j] = min(1+vv[i-1][j-1],vv[i][j]);
                        
                }
            }
            //ret
            return vv[row][col];
        }
    };

--------------------

# 二、不同的子序列 #

[LC36 不同的子序列][LC36]

> 题目描述：  
> 给定两个字符串S和T，返回S子序列等于T的不同子序列个数有多少个？  
> 字符串的子序列是由原来的字符串删除一些字符（也可以不删除）在不改变相对位置的情况下的剩余字符（例如，"ACE"is a subsequence of"ABCDE"但是"AEC"不是）  
> 例如：  
> S=“nowcccoder”, T = “nowccoder”  
> 返回3

> 状态定义怎么写，其实和上题类似，我们的变量只给一个的话，是不好往后面推导的，所以我们这边用F（i，j）表示前S的前i个字符和T的前j个字符的不同子序列个数

> 状态转换，解决这个就基本解决这道题了，我们怎么思考这个问题呢，看S=“nowcccoder”, T = “nowccoder”，的这组测试用例，其实很难说一下子就有思路，我们画个二维图帮助大家理解。

**二维图我们S=“nowccc”, T = “nowcc”，方便大家理解**![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjM0NDQwMQ_size_16_color_FFFFFF_t_70]

> 重点观察 （6，4）这个位置  
> 情况一：**当第i个字符和第j个字符相同时**，可以看出（6，4）位置的组成其实就是（5，5）+（5，4）组成的，为什么是这样，其实F（i，j） 就是考虑第i个元素是否需要，不需要为一种情况，需要为一种情况，其中（5，5）对应不需要第i个元素，而（5，4）对应需要第i个元素  
> 所以我们的转换方程出来了：F（i，j）=F（i-1，j-1）+F（i，j-1）  
> 情况二：**当第i个字符和第j个字符不相同时**  
> **即 F（i，j）=F（i，j-1），即我们的(5,4)的第i个元素和第j个元素若不想等则与他无关**

**再给一个位置的数据验证**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjM0NDQwMQ_size_16_color_FFFFFF_t_70 1]  
同理我们可以看出 （5，4）位置也是如此，**（5，3）这个位置为什么不使用？ - - 其实是因为如果我们不清楚 i ==5的时候第五个字符是否有被使用到，当然我们给的测试用例是没有使用到第五个字符的，所以我们不可以使用这个位置，因为只有确保使用到当前i个字符我们才好推导下一个状态，类似我们上一章讲到的[最大连续子数组和(Maximum Subarray)][Maximum Subarray]**

--------------------

> **初始化**：看到大家肯定都熟能生巧了，我们刚刚所F（i，j）用到了F（i-1，j）和F(i-1 ,j-1),所以我们给一个二维数组的时候多给**多一行一列**。  
> 初始化的内容\*\*F（i，0）\*\*表示从i个字符的找到子序列和空串相同。  
> **第一种解释：空集是所有集的子集，所以我们F（i，0）全部置成1。**  
> **第二种解释，当我们的元素一开始不相等，直到S第i个元素，才和T的第一个元素相等的时候，我们需要一个空串作为辅助状态，如下图，图中有解释**  
> **到F（0，j）就好解决了，我们的S为空字符串就没有什么子序列了，所以F（0，j） 全部置成0**  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjM0NDQwMQ_size_16_color_FFFFFF_t_70 2]

--------------------

# 总结 #

> 讲到这里，我们的动规也就告一段落了，之后我会发布继续更新算法，下节的算法会给大家带来搜索，广度遍历搜索和深度遍历搜索。  
> 制作不易，一键三连！！！！！！！！

[Link 1]: https://blog.csdn.net/weixin_52344401/article/details/119655486?spm=1001.2014.3001.5501
[LC77]: https://www.nowcoder.com/practice/81d7738f954242e5ade5e65ec40e5027?tpId=46&tqId=29106&tPage=1&rp=1&ru=/ta/leetcode&qru=/ta/leetcode/question-ranking
[LC36]: https://www.nowcoder.com/practice/ed2923e49d3d495f8321aa46ade9f873?tpId=46&tqId=29065&tPage=1&rp=1&ru=/ta/leetcode&qru=/ta/leetcode/question-ranking
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjM0NDQwMQ_size_16_color_FFFFFF_t_70]: /images/20220829/f200fd2763ca4e1bab17279fe5f6f598.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjM0NDQwMQ_size_16_color_FFFFFF_t_70 1]: /images/20220829/6604af6fc2a94021b70fe4bfb80a2321.png
[Maximum Subarray]: https://www.nowcoder.com/practice/459bd355da1549fa8a49e350bf3df484?tpId=13&tqId=11183&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjM0NDQwMQ_size_16_color_FFFFFF_t_70 2]: /images/20220829/f9dab1460a914fa1a56c0b1fd0ae19d2.png