代码随想录第五十九天 | 115.差别的子序列，583. 两个字符串的删除利用， 72. 编辑间隔

115.差别的子序列

看完想法：这个标题只涉及删减，具体是 s 字符串的删减，t 不须要动。当s[ i ] == t[j]时，有两种环境，可以用s也可以不消，而s !=t[j]时只有一种环境，须要删除s进一步比力。在初始化时，不要臆想，要根据dp [j]界说初始化。dp[0] 体现：以i-1为末端的s可以任意删除元素，出现空字符串的个数，肯定为1；dp[0][j]肯定都是0，s如论怎样也变成不了t；dp[0][0]应该是1，空字符串s，可以删除0个元素，变成空字符串t。

2. int numDistinct(string s, string t) {
3.         //uint64_t代表unsigned long int，有8个字节，直接用int会溢出
4.         vector<vector<uint64_t>> dp(s.size() + 1, vector<uint64_t>(t.size() + 1));
5.         //dp数组初始化
6.         for (int i = 0; i < s.size(); i++) dp[i][0] = 1;
7.         for (int j = 1; j < t.size(); j++) dp[0][j] = 0;
8.         //dp递推
9.         for (int i = 1; i <= s.size(); i++) {
10.             for (int j = 1; j <= t.size(); j++) {
11.                 if (s[i - 1] == t[j - 1]) {
12.                     dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
13.                 } else {
14.                     dp[i][j] = dp[i - 1][j];
15.                 }
16.             }
17.         }
18.         return dp[s.size()][t.size()];
20.     }

复制代码

583. 两个字符串的删除利用

看完想法：这里删除利用须要取最小值，假如s == t[j]，不消作利用，继承前次dp;假如不太雷同就须要删除，包罗3种环境，删除s / 删除t / 两个都删。

2. int minDistance(string word1, string word2) {
3.         //dp初始化
4.         vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1, 0));
5.         //此处以要注意，下标为i-1的字符串变成0，需要i次操作
6.         for(int i = 0; i<= word1.size();i++) dp[i][0] = i;
7.         for (int j = 0; j <= word2.size(); j++) dp[0][j] = j;
8.         //dp迭代
9.         for (int i = 1; i <= word1.size(); i++) {
10.             for (int j = 1; j <= word2.size(); j++) {
11.                 if (word1[i - 1] == word2[j - 1]) {
12.                     dp[i][j] = dp[i - 1][j - 1];
13.                 } else {
14.                     dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
15.                 }
16.             }
17.         }
18.         return dp[word1.size()][word2.size()];

复制代码

 72. 编辑间隔

看完想法：在举行dp迭代时，删除元素和添加元素可以公用一个式子，由于删除word1和添加word2时等价的，利用数都一样；更换元素也只有一次利用数dp[j] = dp[i - 1][j - 1] + 1。综上，dp[j]取3个式子中的最小值。

2. int minDistance(string word1, string word2) {
3.         vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1, 0));
4.         //初始化，和之前的题目大同小异，结尾为i-1的word1如何变成0
5.         for(int i = 0; i<= word1.size(); i++) dp[i][0] = i;
6.         for(int i = 0; i<= word2.size(); i++) dp[0][i] = i;
7.         //dp迭代，注意0已经初始化，要从i, j =1开始
8.         for(int i =1; i<=word1.size() ;i++){
9.             for(int j = 1; j<=word2.size(); j++){
10.                 //这需要分当前遍历的word1和word2元素相等/不相等
11.                 //相等不做操作，不相等要增删减
12.                 if(word1[i-1] == word2[j-1]) dp[i][j] = dp[i-1][j-1];
13.                 else{
14.                 //min操作（中间还需要一个{}），针对3个及以上的元素
15.                 dp[i][j] = min({dp[i-1][j] , dp[i][j-1] , dp[i-1][j-1]}) + 1;
16.                 }
17.             }
18.         }
19.         return dp[word1.size()][word2.size()];

复制代码