刷题Day56

1.两个字符串的删除操作

583. 两个字符串的删除操作

1.dp数组的含义：dp[i][j]是i-1位置的word1字母与j-1位置的word2字母为结尾时，两个字符串的删除的数目

2.dp数组的操作：首先if(word1[i-1]==word2[j-1])，此时两个对应末尾位置的字母一致，那么此时不需要删除任何字母，也就是说此时的删除数和前面一次两个字符串比较的删除次数一致，故dp[i][j]=dp[i-1][j-1]；此外如果if(word1[i-1]!=word2[j-1])，说明两个字母不相同，需要删除字母，有两种删除方法，一种删除word1[i-1]，一种删除word2[j-1]，不论他们哪一个删除，都会增加一次删除的次数，我们需要求的是最小的那一次，那么我们就取两个删除数的较小值dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1);

3.初始化：以为其实dp[i][j]是由dp[i-1][j]和dp[i][j-1]推出来的，我们需要初始化dp[i][0]和dp[0][j]，当下标为0时，说明对应的一个字符串一定是空字符串。那么我们能知道对于另外一个下标，我们一定要删除全部才和空字符串一致，即为dp[i][0]=i和dp[0][j]=j。

class Solution {
public:int minDistance(string word1, string word2) {vector<vector<int>>dp(word1.size()+1,vector<int>(word2.size()+1,0));for(int i=0;i<word1.size()+1;i++)dp[i][0]=i;for(int j=0;j<word2.size()+1;j++)dp[0][j]=j;for(int i=1;i<word1.size()+1;i++){for(int j=1;j<word2.size()+1;j++){if(word1[i-1]==word2[j-1])dp[i][j]=dp[i-1][j-1];elsedp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1);}}return dp[word1.size()][word2.size()];}
};

2.编辑距离

72. 编辑距离

1.dp数组的含义：dp[i][j]是i-1位置的word1字母与j-1位置的word2字母为结尾时，两个字符串的修改次数

2.dp数组的操作：首先if(word1[i-1]==word2[j-1])，此时两个对应末尾位置的字母一致，那么此时不需要编辑任何字母，也就是说此时的编辑数和前面一次两个字符串比较的编辑次数一致，故dp[i][j]=dp[i-1][j-1]。此外如果if(word1[i-1]!=word2[j-1])，说明两个字母不相同，那么有三种操作可以做，增删改，但是其实删除和增加是一样的，一个word删除其实在操作次数上和另一个word增加是没有区别的，那么其实就是两个删和改。对于删除就是min(dp[i-1][j]+1,dp[i][j-1]+1)，对于改，意思其实就是将所谓的word1[i-1]和word2[j-1]变为一样的，那么其实就是dp[i][j]在dp[i-1][j-1]的基础上把两个都改了，操作加一，所有条件为dp[i-1][j-1]+1。取最小值dp[i][j]=min(dp[i-1][j-1]+1,min(dp[i-1][j]+1,dp[i][j-1]+1));

class Solution {
public:int minDistance(string word1, string word2) {vector<vector<int>>dp(word1.size()+1,vector<int>(word2.size()+1,0));for(int i=0;i<word1.size()+1;i++)dp[i][0]=i;for(int j=0;j<word2.size()+1;j++)dp[0][j]=j;for(int i=1;i<word1.size()+1;i++){for(int j=1;j<word2.size()+1;j++){if(word1[i-1]==word2[j-1])dp[i][j]=dp[i-1][j-1];elsedp[i][j]=min(dp[i-1][j-1]+1,min(dp[i-1][j]+1,dp[i][j-1]+1));}}return dp[word1.size()][word2.size()];}
};

刷题Day57

1. 回文子串

647. 回文子串

1.如果只是判断两个字母，那么无法知道中间的是否是回文，所以根据这一问题能延申出一个基本事实，我们如果想要实现动态规划的思路，那么一定想要：1.i和j位置的字母相同；2.i+1和j-1里面的字母是回文的。这才能推出ij位置是回文

2.dp数组的含义：dp[i][j]为i到j范围内，子字符串是否是回文子串，是则存为true

3.dp数组的操作：如果s[i] == s[j]，其实有三种情况，1.i==j，此时不需要考虑直接true，2.i+1==j，此时为两个字母，也不需要考虑，直接true 3.则需要判断是否dp[i + 1][j - 1] == true，如果是则dp[i][j] 为true

class Solution {
public:int countSubstrings(string s) {vector<vector<bool>>dp(s.size(), vector<bool>(s.size(), false));int ret = 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 || (j - i > 1 && dp[i + 1][j - 1] == true)){dp[i][j] = true;ret++;}}}}return ret;}
};

2.最长回文子序列

516. 最长回文子序列

1.由于是子序列，所以我们需要定义的dp数组和条件会多一些限制

2.dp数组的含义：dp[i][j]为i到j范围内子序列的最大回文

3.dp数组的操作：

如果s[i] == s[j]，说明此时可构成回文子序列，那么我们需要对数组进行更新，1.如果i==j，dp[i][j]=1，表示只有一个回文串 2.如果如果i==j-1，dp[i][j]=2，表示有两个个回文串 3.如果i<j-1，那么dp[i][j] = dp[i + 1][j - 1] + 2，表示之间的子序列最大回文数加i和j位置的两个字母构成更大的回文。

如果s[i] != s[j]，我们那么此时i到j位置的最大回文串其实继承于里面的最大回文情况，我们需要比较 i+1位置到j位置和 i位置到j-1位置的回文串，哪个更大，再更新。条件为dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);

class Solution {
public:int longestPalindromeSubseq(string s) {vector<vector<int>>dp(s.size(), vector<int>(s.size(), 0));for (int i = s.size() - 1; i >= 0; i--){for (int j = i; j < s.size(); j++){if (s[i] == s[j]){if (i == j)dp[i][j] = 1;else if (j - i == 1)dp[i][j] = 2;elsedp[i][j] = dp[i + 1][j - 1] + 2;}elsedp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);}}return dp[0][s.size() - 1];}
};