代码随想录| 编辑距离
判断子序列[https://leetcode.cn/problems/is-subsequence/description/]
题意：给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
思路：从动态规划， dp[i][j] 表示s的前i-1个元素和t的前j-1个元素相同的子序列元素的个数。
还要对dp初始化。dp[i][0] 表示在t空串的情况下，s的前i-1个字符串的相等的情况。 都设为0 ； dp[0][j] 表示在s为空串的情况下与s的前j-1个字符串相等的情况。
状态转移：
if(s[i-1] == t[j-1])
dp[i][j] = dp[i-1][j-1] +1 ; // 表示 个数加1 。
else
dp[i][j] = dp[i][j-1] ; // 表示现在的状态是s的前一个元素的状态。
不同子序列
题意：两个字符串s, t 统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 109 + 7 取模。
思路：dp[i][j] 表示在s的前i-1个字符的情况下，t的前j-1个字符出现的次数。
dp初始化：dp[i][0] 表示s的前i-1个字符，t空串出现的次数为1 。
dp[0][j]= 0 表示s为空串的情况 ， t串出现的次数为0 。
因为有这样的例子： s：bagg 和 t：bag ，s[3] 和 t[2]是相同的，但是字符串s也可以不用s[3]来匹配，即用s[0]s[1]s[2]组成的bag。
dp[i][j] = dp[i-1][j-1] + dp[i-1][j] ; // 由s的上一个字符来达到。
动态转移：
if(s[i-1] == t[j-1])
// 分别由上一个迭代的dp[i][j] 的个数和dp[i-1][j]表示删除掉s的当前遍历元素的个数组成。
dp[i][j] = dp[i-1][j-1] + dp[i-1][j] ;
else
dp[i][j] = dp[i-1][j] ;
代码
class Solution {
public:int numDistinct(string s, string t) {const int N = 1e3+10 ;// 可以映射为删除s的元素的方式使得s最后与t相等的个数vector<vector<uint64_t >> dp(s.size()+10 , vector<uint64_t>(t.size() + 10 , 0)) ; // dp[i][j] 表示在s的前i-1的子串(子序列)出现t的前j-1个子串的个数。 for(int i = 0 ; i < s.size() ;++ i){dp[i][0] = 1; // 表示s的前i-1个子串，如何删除达到空字符串。 }// dpfor(int j = 1 ; j < t.size() ; ++ j ){dp[0][j] = 0 ; // 表示空字符串无论如何删除都达到不了j的状态。 }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] ; // 分别由上一个迭代的dp[i][j] 的个数和dp[i-1][j]表示删除掉s的当前遍历元素的个数组成。 }else{dp[i][j] = dp[i-1][j] ; }}for(int j = 0 ; j <= 3 ; ++ j){for(int i = 0 ; i <= 7 ; ++i){cout<<dp[i][j]<<" " ; }cout<<endl ; }return dp[s.size()][t.size()] ; }
};
两个字符串的删除操作
题意：给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。
思路：dp[i][j] 表示word1在i-1和word2在j-1之前相同的最小步数。
动态转移：
当word1[i-1] == word2[j-1]
dp[i][j] = dp[i-1][j-1] ;
当word1[i-1] != word2[j-1]
dp[i][j] = min (dp[i-1][j] +1 , dp[i][j-1]+1 , dp[i-1][j-1] +2 ) ; // 包括删除word1这个i元素， 等于dp[i-1][j] 的状态 +1 加一表示加上删除操作。 dp[i][j-1] +1 ; 和表示dp[i-1][j] +1 和两个字符串 都要删除自己末尾的元素。
代码
class Solution {
public:int minDistance(string word1, string word2) {vector<vector<uint64_t>> dp(word1.size()+10, vector<uint64_t>(word2.size()+10 , 0 )) ; // dp[i][j] 表示使word1的前i-1字符和word2的前j-1个字符的最小步数。 for(int i = 0 ; i <= word1.size() ; ++ i){dp[i][0] = i ; // 步数是i+1 删除i个字符串。 可以达到word2为空的状态。 }for(int j = 0 ; j <= word2.size() ; ++ j){dp[0][j] = j ; // 步数是j+1 ; 删除j个字符串， 可以达到word1为空的状态}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] +1 ,min( dp[i][j-1] +1 , dp[i-1][j-1] +2 ) ) ; // 是要在dp[i-1 ] [j] 的状态下加1 。 和dp[i][j-1] 的状态下加1 或者 dp[i-1][j-1]的状态下加2中选一个最小的。 }}return dp[word1.size()][word2.size()] ; }
};
以上几个题是为最短编辑距离服务的
最短编辑距离：
给定两个单词word1和word2 。请返回将 word1 转换成 word2 所使用的最少操作数 。
- word2添加一个元素，相当于word1删除一个元素，例如 word1 = “ad” ，word2 = “a”，word2添加一个元素d，也就是相当于word1删除一个元素d，操作数大小一样！
思路：
dp[i][j] 表示在word1在i-1之前和 word2在j-1之前的最少操作次数。
如果word1[i-1] == word2[j-1] ; 那么
dp[i][j] =dp[i-1][j-1] ;
否则
dp[i][j] = min(dp[i-1][j] +1, dp[i][j-1] +1 , dp[i-1][j-1] +1 ) ; ; // dp[i-1][j-1] +1 表示修改 。
return dp[word1.size() ][word2.size()] ;