代碼隨想錄算法訓練營第51天 [115.不同的子序列 583. 兩個字符串的刪除操作 72. 編輯距離 ]

---

一、115.不同的子序列

鏈接: 代碼隨想錄.
思路：dp[i][j] 以t[j-1]為結尾的字符串在 以s[i-1]為結尾的字 符串出現個數
相等的時候 dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
不相等的時候 dp[i][j] = dp[i - 1][j];
做題狀態：看解析后做出來了

class Solution {
public:int numDistinct(string s, string t) {// dp[i][j] 以t[j-1]為結尾的字符串在 以s[i-1]為結尾的字 符串出現個數vector<vector<uint64_t>> dp(s.size() + 1, vector<uint64_t>(t.size() + 1, 0));dp[0][0] = 1;for(int i = 0;i<s.size();i++){dp[i][0] = 1;}for (int i = 1; i <= s.size(); i++) {for (int j = 1; j <= t.size(); 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.size()][t.size()];}
};

二、583. 兩個字符串的刪除操作

鏈接: 代碼隨想錄.
思路：看注釋
做題狀態：看解析后做出來了

class Solution {
public:int minDistance(string word1, string word2) {// dp[i][j]//  以i-1為結尾的字符串word1，和以j-1位結尾的字符串word2，想要達到相等，所需要刪除元素的最少次數vector<vector<int>> dp(word1.size() + 1,vector<int>(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 {// 不相等 要么刪word1 要么刪word2 要么都刪dp[i][j] = min({dp[i - 1][j] + 1, dp[i][j - 1] + 1,dp[i - 1][j - 1] + 2});}}}return dp[word1.size()][word2.size()];}
};

三、72. 編輯距離

鏈接: 代碼隨想錄.
思路：看注釋，不相等的時候的增、刪、改
做題狀態：看解析后做出來了

class Solution {
public:int minDistance(string word1, string word2) {// dp[i][j]vector<vector<int>> dp(word1.size() + 1,vector<int>(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 {// 增// word1里增加一個，相當于word2里刪除一個，操作次數和刪差不多// 刪 // dp[i][j] = min(dp[i-1][j],dp[i][j-1])// 分別對應刪除word1 和 刪除word2 // 改 // 替換一個后 word1[i-1] == word2[j-1]// 相當于在dp[i-1][j-1]的基礎上多操作一步//    所以是dp[i - 1][j - 1] + 1dp[i][j] = min({dp[i - 1][j] + 1, dp[i][j - 1] + 1,dp[i - 1][j - 1] + 1});}}}return dp[word1.size()][word2.size()];}
};