小米路由 做网站,钦州建站哪家好,宁波seo服务推广平台,上上海网站建设设计题1#xff1a;
指路#xff1a;72. 编辑距离 - 力扣#xff08;LeetCode#xff09;
思路与代码#xff1a;
关于dp数组的定义#xff0c;我们定义一个二维数组dp[i][j]#xff0c;其含义为以i-1为结尾的字符串word1和以j-1为结尾的字符串word2#xff0c;最近编辑…题1
指路72. 编辑距离 - 力扣LeetCode
思路与代码
关于dp数组的定义我们定义一个二维数组dp[i][j]其含义为以i-1为结尾的字符串word1和以j-1为结尾的字符串word2最近编辑距离为dp[i][j]。关于递推公式如果数组1和数组2中内容相等此时无须做任何操作就等于下标为i-1和j-1的编辑距离也就是dp[i][j]dp[i-1][j-1]。当数组1和数组2中内容不同时此时有三种操作增、删、改。注意当word1和word2中内容不相同时不一定是单单改变其中一个变成另一个也可以选择两者同时改变向对方靠近。删除word1的一个字符是dp[i-1][j]1替换字符为dp[i-1][j-1]1删除word2中字符(相对于word1为增加字符)即为dp[i][j-1]1取最小值即为 dp[i][j] min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]}) 1。那么在初始化环节dp[i][0]的含义为以下标i-1为结尾的字符串word1和空字符串word2的最近编辑距离为dp[i][0]得到dp[i][0]i同理dp[0][j]j。对于遍历顺序很显然是从上到下从左到右最后打印即可。代码如下
class Solution {
public:int minDistance(string word1, string word2) {vectorvectorint dp(word1.size() 1, vectorint(word2.size() 1, 0));for (int i 0; i word1.size(); i) dp[i][0] i;for (int j 0; j word2.size(); j) dp[0][j] j;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], dp[i][j - 1], dp[i - 1][j - 1]}) 1;}}}return dp[word1.size()][word2.size()];}
};
题2
指路647. 回文子串 - 力扣LeetCode
思路与代码
定义一个数组dp[i][j]其含义为在i和j的范围内如果i和j对应的值相等且子串如果是回文串那么这个以i和j为范围的字符串就是回文子串其中分为三种情况首先i和j相等那么显然这个字符串就是只有一个字符的字符串肯定是一个回文串遇到符合条件的回文串时计数器加1其次如果i和j相差为1也就是i和j相邻此时如果s[i]等于s[j]那么这也是一个回文字符串最后一种情况为i和j相差大于1也就是它们之中有一个子串此时将i定义为数组始位置j定义为尾位置在判断s[i]等于s[j]后再进一步将i和j各往前移位一位也就是i1和j-1的位置如果也成立继续判断得到回文子串的判断。注意我们在i和j位置的数值也要判断的是i1和j-1的位置的数值那么在二维数组中对应的位置就是[i,j]的左下方位置换句话来说由左下方向右上方判断也就是从左到右从下往上循环。最后输出即可。
class Solution {
public:int countSubstrings(string s) {if (s.size() 1) return s.size();vectorvectorbool dp(s.size(), vectorbool(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) {result;dp[i][j] true;}else if (dp[i 1][j - 1]) {result;dp[i][j] true;}}}}return result;}
};
题3
指路516. 最长回文子序列 - 力扣LeetCode
思路与代码
本题与上题的区别在于子串和子序列的区别子串须连续子序列则不需要。定义一个数组dp[i][j]其含义为字符串s[i, j]范围内最长的回文子序列的长度为d[i][j]。递推公式中依旧是回文判断s[i]与s[j]的相等状况就好。如果二者相同那么dp[i][j]dp[i1][j-1]2(加2是因为首尾元素也是回文子序列的一部分)如果二者不相同则说明首尾元素不能同时加入子序列的队伍那么尝试首尾元素分开添加取较大值即可即dp[i][j]max(dp[i1][j], dp[i][j-1])。这里的遍历顺序如上题所言从下往上从左往右最后打印即可。代码如下
class Solution {
public:int longestPalindromeSubseq(string s) {vectorvectorint dp(s.size(), vectorint(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];}
};
动态规划的小总结
呼~动态规划终于告一段落了感觉比起子序列问题我更喜欢股票类问题。但是无外乎就五步定义dp数组及其定义推断递推公式初始化dp数组确定遍历顺序最后打印dp数组。好累先这样。
