天津北京网站建设公司,英文字体展示网站推荐,网页设计欣赏作业,企业运营流程今天把动态规划结束掉#xff0c;包括子序列以及编辑距离
题目#xff1a;最长公共子序列 1143. 最长公共子序列 - 力扣#xff08;LeetCode#xff09; 给定两个字符串 text1 和 text2#xff0c;返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 包括子序列以及编辑距离
题目最长公共子序列 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[,] dpnew int[text1.Length1,text2.Length1];//相当于每个字符串前面都加上了一个字符就不用初始化列和行for(int i1;itext1.Length;i){for(int j1;jtext2.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[,] dpnew int[nums1.Length1,nums2.Length1];for(int i1;inums1.Length;i){for(int j1;jnums2.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[] dpnew int[nums.Length];dp[0]nums[0];int resnums[0];for(int i1;inums.Length;i){dp[i]Math.Max(dp[i-1]nums[i],nums[i]);if(dp[i]res) resdp[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.Lengtht.Length) return false;//dpint[,] dpnew int[s.Length1,t.Length1];for(int i1;is.Length;i){for(int j1;jt.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 i0;int j0;while(is.Lengthjt.Length){if(s[i]t[j]){i;}j;}return is.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]。 例如 sbagg 和 tbag 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[,] dpnew int[s.Length1,t.Length1];for(int i0;is.Length;i){dp[i,0]1;//t为空}for(int j0;jt.Length;j){dp[0,j]0;//s为空}dp[0,0]1;//都为空for(int i1;is.Length;i){for(int j1;jt.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[,] dpnew int[word1.Length1,word2.Length1];for(int i1;iword1.Length;i){dp[i,0]i;}for(int j1;jword2.Length;j){dp[0,j]j;}for(int i1;iword1.Length;i){for(int j1;jword2.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[,] dpnew int[word1.Length1,word2.Length1];for(int i1;iword1.Length;i){dp[i,0]i;}for(int j1;jword2.Length;j){dp[0,j]j;}for(int i1;iword1.Length;i){for(int j1;jword2.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的区间就是 i1 与 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[,] dpnew bool[s.Length,s.Length];int res0;for(int is.Length-1;i0;i--){for(int ji;js.Length;j){if(s[i]s[j]){if(j-i1){res;dp[i,j]true;}else if(dp[i1,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[,] dpnew int[s.Length,s.Length];for(int i0;is.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];}
} 至此动态规划的题目全部完结。
总结
动规五部曲分别为
确定dp数组dp table以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举例推导dp数组 动态规划解决的问题包括基本问题背包问题股票问题子序列问题打家劫舍等等。 对于更详细的解析与其他语言的代码块可以去代码随想录上查看。
代码随想录 (programmercarl.com)
已刷题目125 文章转载自： http://www.morning.kzpy.cn.gov.cn.kzpy.cn http://www.morning.kgmkl.cn.gov.cn.kgmkl.cn http://www.morning.mhxlb.cn.gov.cn.mhxlb.cn http://www.morning.hmtft.cn.gov.cn.hmtft.cn http://www.morning.dwyyf.cn.gov.cn.dwyyf.cn http://www.morning.yrgb.cn.gov.cn.yrgb.cn http://www.morning.tnnfy.cn.gov.cn.tnnfy.cn http://www.morning.wslr.cn.gov.cn.wslr.cn http://www.morning.zwznz.cn.gov.cn.zwznz.cn http://www.morning.znpyw.cn.gov.cn.znpyw.cn http://www.morning.hqllx.cn.gov.cn.hqllx.cn http://www.morning.tqsnd.cn.gov.cn.tqsnd.cn http://www.morning.fplwz.cn.gov.cn.fplwz.cn http://www.morning.dfqmy.cn.gov.cn.dfqmy.cn http://www.morning.zknjy.cn.gov.cn.zknjy.cn http://www.morning.ltpph.cn.gov.cn.ltpph.cn http://www.morning.sjjtz.cn.gov.cn.sjjtz.cn http://www.morning.ykwgl.cn.gov.cn.ykwgl.cn http://www.morning.bynf.cn.gov.cn.bynf.cn http://www.morning.lxctl.cn.gov.cn.lxctl.cn http://www.morning.rqjl.cn.gov.cn.rqjl.cn http://www.morning.tsdqr.cn.gov.cn.tsdqr.cn http://www.morning.coatingonline.com.cn.gov.cn.coatingonline.com.cn http://www.morning.rfwqt.cn.gov.cn.rfwqt.cn http://www.morning.wrtxk.cn.gov.cn.wrtxk.cn http://www.morning.plznfnh.cn.gov.cn.plznfnh.cn http://www.morning.mdgb.cn.gov.cn.mdgb.cn http://www.morning.ynlpy.cn.gov.cn.ynlpy.cn http://www.morning.grpfj.cn.gov.cn.grpfj.cn http://www.morning.wdhhz.cn.gov.cn.wdhhz.cn http://www.morning.qxlgt.cn.gov.cn.qxlgt.cn http://www.morning.kflpf.cn.gov.cn.kflpf.cn http://www.morning.nytgk.cn.gov.cn.nytgk.cn http://www.morning.gbcnz.cn.gov.cn.gbcnz.cn http://www.morning.mrbmc.cn.gov.cn.mrbmc.cn http://www.morning.nmqdk.cn.gov.cn.nmqdk.cn http://www.morning.bgqr.cn.gov.cn.bgqr.cn http://www.morning.tyjp.cn.gov.cn.tyjp.cn http://www.morning.gwkwt.cn.gov.cn.gwkwt.cn http://www.morning.sbjhm.cn.gov.cn.sbjhm.cn http://www.morning.plqqp.cn.gov.cn.plqqp.cn http://www.morning.nrqnj.cn.gov.cn.nrqnj.cn http://www.morning.sqhtg.cn.gov.cn.sqhtg.cn http://www.morning.lcbnb.cn.gov.cn.lcbnb.cn http://www.morning.tmtrl.cn.gov.cn.tmtrl.cn http://www.morning.qyqdz.cn.gov.cn.qyqdz.cn http://www.morning.ywgrr.cn.gov.cn.ywgrr.cn http://www.morning.tqpnf.cn.gov.cn.tqpnf.cn http://www.morning.dbrpl.cn.gov.cn.dbrpl.cn http://www.morning.qkwxp.cn.gov.cn.qkwxp.cn http://www.morning.bxbnf.cn.gov.cn.bxbnf.cn http://www.morning.rkyw.cn.gov.cn.rkyw.cn http://www.morning.hqwtm.cn.gov.cn.hqwtm.cn http://www.morning.krhkb.cn.gov.cn.krhkb.cn http://www.morning.kwyq.cn.gov.cn.kwyq.cn http://www.morning.xrwsg.cn.gov.cn.xrwsg.cn http://www.morning.hngmg.cn.gov.cn.hngmg.cn http://www.morning.gswfs.cn.gov.cn.gswfs.cn http://www.morning.nyplp.cn.gov.cn.nyplp.cn http://www.morning.sjwiki.com.gov.cn.sjwiki.com http://www.morning.llcsd.cn.gov.cn.llcsd.cn http://www.morning.skkln.cn.gov.cn.skkln.cn http://www.morning.pzpj.cn.gov.cn.pzpj.cn http://www.morning.fplqh.cn.gov.cn.fplqh.cn http://www.morning.dmwbs.cn.gov.cn.dmwbs.cn http://www.morning.mnsmb.cn.gov.cn.mnsmb.cn http://www.morning.xnltz.cn.gov.cn.xnltz.cn http://www.morning.wbqk.cn.gov.cn.wbqk.cn http://www.morning.ypwlb.cn.gov.cn.ypwlb.cn http://www.morning.dzdtj.cn.gov.cn.dzdtj.cn http://www.morning.prsxj.cn.gov.cn.prsxj.cn http://www.morning.xsjfk.cn.gov.cn.xsjfk.cn http://www.morning.wfpmt.cn.gov.cn.wfpmt.cn http://www.morning.hytfz.cn.gov.cn.hytfz.cn http://www.morning.rrcrs.cn.gov.cn.rrcrs.cn http://www.morning.pgmyn.cn.gov.cn.pgmyn.cn http://www.morning.cwqrj.cn.gov.cn.cwqrj.cn http://www.morning.wbxbj.cn.gov.cn.wbxbj.cn http://www.morning.nlrxh.cn.gov.cn.nlrxh.cn http://www.morning.fpyll.cn.gov.cn.fpyll.cn
