算法日记 36-38day 动态规划

今天把动态规划结束掉，包括子序列以及编辑距离

题目：最长公共子序列

1143. 最长公共子序列 - 力扣（LeetCode）

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

• 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

题目分析：

        上一题求得公共子数组，这一题换成了子序列，子序列只有相对位置不改变。dp五部曲来看，dp[i,j]表示得是以i-1结尾得字符串和以j-1结尾得字符串得最长公共子序列为dp[i,j]。这里之所以写成i-1和j-1主要是为了减少初始化得麻烦。同样的，你也可以表示为i,j。上一篇得题目中写了具体得情况。

         递推公式，对于i-1和j-1来说，有两个可能，一个相同一个不同。

相同：

        既然相同，那么的dp[i,j]=dp[i-1,j-1]+1;

不同：

        如果text1[i - 1] 与 text2[j - 1]不相同，那就看看text1[0, i - 2]与text2[0, j - 1]的最长公共子序列 和 text1[0, i - 1]与text2[0, j - 2]的最长公共子序列，取最大的。

即：dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

public class Solution {public int LongestCommonSubsequence(string text1, string text2) {int[,] dp=new int[text1.Length+1,text2.Length+1];//相当于每个字符串前面都加上了一个字符，就不用初始化列和行for(int i=1;i<=text1.Length;i++){for(int j=1;j<=text2.Length;j++){if(text1[i-1]==text2[j-1]){dp[i,j]=dp[i-1,j-1]+1;}else{dp[i,j]=Math.Max(dp[i-1,j],dp[i,j-1]);}}}return dp[text1.Length,text2.Length];}
}

题目：不相交的线

1035. 不相交的线 - 力扣（LeetCode）

在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。

现在，可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直线需要同时满足：

•  nums1[i] == nums2[j]
• 且绘制的直线不与任何其他连线（非水平线）相交。

请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。

以这种方法绘制线条，并返回可以绘制的最大连线数。

题目分析：     

        绘制一些连接两个数字 A[i] 和 B[j] 的直线，只要 A[i] == B[j]，且直线不能相交！

直线不能相交，这就是说明在字符串A中 找到一个与字符串B相同的子序列，且这个子序列不能改变相对顺序，只要相对顺序不改变，链接相同数字的直线就不会相交。

 这么看来，这一题和上一题是一样得了

public class Solution {public int MaxUncrossedLines(int[] nums1, int[] nums2) {int[,] dp=new int[nums1.Length+1,nums2.Length+1];for(int i=1;i<=nums1.Length;i++){for(int j=1;j<=nums2.Length;j++){if(nums1[i-1]==nums2[j-1]){dp[i,j]=dp[i-1,j-1]+1;}else{dp[i,j]=Math.Max(dp[i-1,j],dp[i,j-1]);}}}return dp[nums1.Length,nums2.Length];}
}

题目：最大子序和

53. 最大子数组和 - 力扣（LeetCode）

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组是数组中的一个连续部分。

题目分析： 

        这一题之前用贪心做过，。不过主要来看看动态规划得方法。

dp[i]:表示0-i的区间内，最大的子数组和为dp[i]

那么递推公式就很清楚了dp[i]=dp[i-1]+nums[i],不过这个值可能会变小，所以和它本身取最大。

dp[i]=max(dp[i-1]+nums[i],nums[i])

dp[i]取决于dp[i-1],所以初始化dp[0]即可

public class Solution {public int MaxSubArray(int[] nums) {int[] dp=new int[nums.Length];dp[0]=nums[0];int res=nums[0];for(int i=1;i<nums.Length;i++){dp[i]=Math.Max(dp[i-1]+nums[i],nums[i]);if(dp[i]>res) res=dp[i];}return res;}
}

题目：判断子序列

392. 判断子序列 - 力扣（LeetCode） 

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

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

 题目分析：

        从这一题开始就是编辑距离类型的题目了。这一题也可以使用双指针的方法，我会放在后面，主要看动态规划。

其实本质上和最长公共子序列差不多，不过多了删除这个操作。来看看它的dp

dp[i,j]:表示以i-1结尾的s和以j-1结尾的t相同子序列长度为dp[i,j]

同样的，对于i和j的字符而言，有相同和不相同两个。相同时dp[i,j]=dp[i-1,j-1]+1.

主要看不同。如果说这个字符不同，我们删去的话，dp[i,j]应该是dp[i,j-1]。取j-1的字符范围其实就是将j给删除了。

初始化    

        从递推公式可以看出dp[i][j]都是依赖于dp[i - 1][j - 1] 和 dp[i][j - 1]，所以dp[0][0]和dp[i][0]是一定要初始化的。

这里大家已经可以发现，在定义dp[i][j]含义的时候为什么要表示以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度为dp[i][j]。

因为这样的定义在dp二维矩阵中可以留出初始化的区间，如图：

//动态规划
public class Solution {public bool IsSubsequence(string s, string t) {if(s.Length>t.Length) return false;//dpint[,] dp=new int[s.Length+1,t.Length+1];for(int i=1;i<=s.Length;i++){for(int j=1;j<=t.Length;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];}}}return dp[s.Length,t.Length]==s.Length;}
}//双指针
public class Solution {public bool IsSubsequence(string s, string t) {int i=0;int j=0;while(i<s.Length&&j<t.Length){if(s[i]==t[j]){i++;}j++;}return i==s.Length;}
}

题目： 不同的子序列

给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 109 + 7 取模。 

题目分析： 

        动规五部曲分析。

dp[i][j]：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。

那么对于s[i-1]和t[j-1]来说，有相同和不相同两种，对于相同，dp[i,j]=dp[i-1,j-1]。除此之外还有一个dp[i,j]=dp[i-1,j]。

        例如： s：bagg 和 t：bag ，s[3] 和 t[2]是相同的，但是字符串s也可以不用s[3]来匹配，即用s[0]s[1]s[2]组成的bag。

当然也可以用s[3]来匹配，即：s[0]s[1]s[3]组成的bag。所以当s[i - 1] 与 t[j - 1]相等时，dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];

当s[i - 1] 与 t[j - 1]不相等时，dp[i][j]只有一部分组成，不用s[i - 1]来匹配（就是模拟在s中删除这个元素），即：dp[i - 1][j]

所以递推公式为：dp[i][j] = dp[i - 1][j];

从递推公式dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]; 和 dp[i][j] = dp[i - 1][j]; 中可以看出dp[i][j] 是从上方和左上方推导而来，如图：，那么 dp[i][0] 和dp[0][j]是一定要初始化的。

public class Solution {public int NumDistinct(string s, string t) {int[,] dp=new int[s.Length+1,t.Length+1];for(int i=0;i<s.Length;i++){dp[i,0]=1;//t为空}for(int j=0;j<t.Length;j++){dp[0,j]=0;//s为空}dp[0,0]=1;//都为空for(int i=1;i<=s.Length;i++){for(int j=1;j<=t.Length;j++){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.Length,t.Length];}
}

题目：两个字符串的删除操作

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

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

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

 题目分析：

        两个字符串相等，那不就是公共子序列吗？这一题其实有一个简单写法，之前写最长公共子序列的时候求出两个的最长子序列，那么两个字符串把多余的部分删掉不久行了吗。这个写法就不多说了。

        dp[i,j]表示0-i的w1变成0-j的w2需要的最小步数。

对于w1[i-1]==w2[j-1]的情况，dp[i,j]=dp[i-1,j-1]。不需要删除

对于不相同的情况，删除可以有三中选择，

情况一：删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

那最后当然是取最小值，所以当word1[i - 1] 与 word2[j - 1]不相同的时候，递推公式：dp[i][j] = min({dp[i - 1][j - 1] + 2, dp[i - 1][j] + 1, dp[i][j - 1] + 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);

public class Solution {public int MinDistance(string word1, string word2) {//以i-1为结尾的字符串word1，和以j-1位结尾的字符串word2，想要达到相等，所需要删除元素的最少次数。int[,] dp=new int[word1.Length+1,word2.Length+1];for(int i=1;i<=word1.Length;i++){dp[i,0]=i;}for(int j=1;j<=word2.Length;j++){dp[0,j]=j;}for(int i=1;i<=word1.Length;i++){for(int j=1;j<=word2.Length;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] + 2, dp[i - 1][j] + 1, dp[i][j - 1] + 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);dp[i,j]=Math.Min(dp[i-1,j]+1,dp[i,j-1]+1);}}}return dp[word1.Length,word2.Length];}
}

 题目：编辑距离

72. 编辑距离 - 力扣（LeetCode）

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

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

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

 题目分析：

        上一题只有删除一种操作，而现在有插入和替换，删除3种操作。其实大差不差，主要看dp的公式。

对于删除而言，dp[i,j]=min(dp[i-1,j],dp[i,j-1]) 具体分析看上一题。

对于插入而言，比如ab,a。实际上对a添加一个b等同于对ab删除一个b,两个的操作步数是一样的，意味着我们不需要取考虑插入，他和删除完全一样

对于替换，word1替换word1[i - 1]，使其与word2[j - 1]相同，此时不用增删加元素。

可以回顾一下，if (word1[i - 1] == word2[j - 1])的时候我们的操作 是 dp[i][j] = dp[i - 1][j - 1] 对吧。

那么只需要一次替换的操作，就可以让 word1[i - 1] 和 word2[j - 1] 相同。

所以 dp[i][j] = dp[i - 1][j - 1] + 1;

初始化部分和之前一样

public class Solution {public int MinDistance(string word1, string word2) {int[,] dp=new int[word1.Length+1,word2.Length+1];for(int i=1;i<=word1.Length;i++){dp[i,0]=i;}for(int j=1;j<=word2.Length;j++){dp[0,j]=j;}for(int i=1;i<=word1.Length;i++){for(int j=1;j<=word2.Length;j++){if(word1[i-1]==word2[j-1]){dp[i,j]=dp[i-1,j-1];}else{dp[i,j]=Math.Min(Math.Min(dp[i-1,j]+1,dp[i,j-1]+1),dp[i-1,j-1]+1);}}}return dp[word1.Length,word2.Length];}
}

题目：回文字串

647. 回文子串 - 力扣（LeetCode）

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

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

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

题目分析： 

         如果我们定义，dp[i] 为 下标i结尾的字符串有 dp[i]个回文串的话，我们会发现很难找到递归关系。dp[i] 和 dp[i-1] ，dp[i + 1] 看上去都没啥关系。

        那么，对于一个回文串来说，他是什么样的呢？

 

对于cbabc而言，中间部分bab是回文串，那整体呢？是不是取决于边界。

此时我们是不是能找到一种递归关系，也就是判断一个子字符串（字符串下标范围[i,j]）是否回文，依赖于，子字符串（下标范围[i + 1, j - 1]）） 是否是回文。

所以我们的dp定义为布尔类型的dp[i][j]：表示区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串，如果是dp[i][j]为true，否则为false。

当s[i]与s[j]不相等，那没啥好说的了，dp[i][j]一定是false。

当s[i]与s[j]相等时，这就复杂一些了，有如下三种情况

• 情况一：下标i 与 j相同，同一个字符例如a，当然是回文子串
• 情况二：下标i 与 j相差为1，例如aa，也是回文子串
• 情况三：下标：i 与 j相差大于1的时候，例如cabac，此时s[i]与s[j]已经相同了，我们看i到j区间是不是回文子串就看aba是不是回文就可以了，那么aba的区间就是 i+1 与 j-1区间，这个区间是不是回文就看dp[i + 1][j - 1]是否为true

初始化为false即可，这里不用多说

那么遍历顺序呢？

从递推公式可以看出来情况三是根据dp[i + 1][j - 1]是否为true，在对dp[i][j]进行赋值true的。

dp[i + 1][j - 1] 在 dp[i][j]的左下角，如图：

所以我们的遍历顺序一定要从下到上，从左到右遍历，这样保证dp[i + 1][j - 1]都是经过计算的。

public class Solution {public int CountSubstrings(string s) {bool[,] dp=new bool[s.Length,s.Length];int res=0;for(int i=s.Length-1;i>=0;i--){for(int j=i;j<s.Length;j++){if(s[i]==s[j]){if(j-i<=1){res++;dp[i,j]=true;}else if(dp[i+1,j-1]){res++;dp[i,j]=true;}}}}return res;}
}

 题目：最长回文子序列

 516. 最长回文子序列 - 力扣（LeetCode）

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

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

 题目分析：

        又是子序列。还是五部曲。

dp[i][j]：字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]。

在判断回文子串的题目中，关键逻辑就是看s[i]与s[j]是否相同。

        如果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]);

dp数组如何初始化

        首先要考虑当i 和j 相同的情况，从递推公式：dp[i][j] = dp[i + 1][j - 1] + 2; 可以看出 递推公式是计算不到 i 和j相同时候的情况。

        所以需要手动初始化一下，当i与j相同，那么dp[i][j]一定是等于1的，即：一个字符的回文子序列长度就是1。

        其他情况dp[i][j]初始为0就行，这样递推公式：dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]); 中dp[i][j]才不会被初始值覆盖

public class Solution {public int LongestPalindromeSubseq(string s) {//字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]。int[,] dp=new int[s.Length,s.Length];for(int i=0;i<s.Length;i++){dp[i,i]=1;}for (int i = s.Length - 1; i >= 0; i--) {for (int j = i + 1; j < s.Length; j++) {if (s[i] == s[j]) {dp[i,j] = dp[i + 1,j - 1] + 2;} else {dp[i,j] = Math.Max(dp[i + 1,j], dp[i,j - 1]);}}}return dp[0,s.Length-1];}
}

 

至此，动态规划的题目全部完结。

总结

动规五部曲分别为：

1. 确定dp数组（dp table）以及下标的含义
2. 确定递推公式
3. dp数组如何初始化
4. 确定遍历顺序
5. 举例推导dp数组

 动态规划解决的问题包括基本问题，背包问题，股票问题，子序列问题，打家劫舍等等。

 

对于更详细的解析与其他语言的代码块，可以去代码随想录上查看。

代码随想录 (programmercarl.com)

已刷题目：125