115.不同的子序列
给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 10^9 + 7 取模。
示例 1：
输入：s = "rabbbit", t = "rabbit"
输出：3
解释：
如下所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
rabbbit
rabbbit
rabbbit
示例 2：
输入：s = "babgbag", t = "bag"
输出：5
解释：
如下所示, 有 5 种可以从 s 中得到 "bag" 的方案。
babgbag
babgbag
babgbag
babgbag
babgbag
提示：
1 <= s.length, t.length <= 1000s和t由英文字母组成
思路：
这道题的确有点难，我们首先设置dp[i][j]为s中前i个元素与t前j个元素相匹配的个数，然后我们还要对j=0和i=0的情况进行判断，如果t为空指针那么s可以找到一个与其相匹配的，那么个数就是1，如果s为空，那么个数就为0，最后进行遍历，当满足s[i-1] = t[i-1]时那么dp[i][j]就为前一个个数加上如果前一个数没匹配上的个数，如果不满足就只是没匹配上的个数，最后返回dp[a1][a2]的值就行了。
解答：
int numDistinct(char* s, char* t) {int a1 = strlen(s);int a2 = strlen(t);unsigned long long** dp = malloc((a1+1)*sizeof(unsigned long long*));for(int i = 0;i <= a1;i++){dp[i] = malloc((a2+1)*sizeof(unsigned long));}for(int i = 0;i <= a1;i++){dp[i][0] = 1;}for(int i = 1;i <= a2;i++){dp[0][i] = 0;}for(int i = 1;i <= a1;i++){for(int j = 1;j <= a2;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[a1][a2];
}
583.两个字符串的删除操作
给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步数。
每步 可以删除任意一个字符串中的一个字符。
示例 1：
输入: word1 = "sea", word2 = "eat"
输出: 2
解释: 第一步将 "sea" 变为 "ea" ，第二步将 "eat "变为 "ea"
示例 2:
输入：word1 = "leetcode", word2 = "etco"
输出：4
提示：
1 <= word1.length, word2.length <= 500word1和word2只包含小写英文字母
思路：
这道题跟上面差不多，都是对两个字符串进行操作，这道题中的dp[i][j]的含义指的是在第i个元素和第j个元素时需要删除操作需要几步，同样也分为相等和不等两种情况，但是这道题的初始化要注意，当i=0和j=0这两种情况下，相当于有一个空字符串，所以我们需要初始化它们，最后返回dp[a1][a2]就可以得到答案了。
解答：
int minDistance(char* word1, char* word2) {int a1 = strlen(word1);int a2 = strlen(word2);int** dp = calloc(a1+1,sizeof(int*));for(int i = 0;i <= a1;i++){dp[i] = calloc(a2+1,sizeof(int));}for(int i = 0;i <= a1;i++){dp[i][0] = i;}for(int j = 0;j <= a2;j++){dp[0][j] = j;}for(int i = 1;i <= a1;i++){for(int j = 1;j <= a2;j++){if(word1[i-1] == word2[j-1]){dp[i][j] = dp[i-1][j-1];}else{dp[i][j] = fmin(fmin(dp[i-1][j]+1,dp[i][j-1]+1),dp[i-1][j-1]+2);}}}return dp[a1][a2];
}
72.编辑距离
给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符
示例 1：
输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
示例 2：
输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')
提示：
0 <= word1.length, word2.length <= 500word1和word2由小写英文字母组成
思路：
我们使用动态规划定义dp[i][j]表示将word1[0...i-1]转化为word2[0...j-1]的最小操作数。初始化时，dp[i][0] = i表示删除操作，dp[0][j] = j表示插入操作。对于每个dp[i][j]，如果word1[i-1]与word2[j-1]相同，dp[i][j] = dp[i-1][j-1]，否则dp[i][j] = fmin(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1。最终dp[a1][a2]就是答案，表示将整个word1转化为word2所需的最小操作次数。
解答：
int minDistance(char* word1, char* word2) {int a1 = strlen(word1);int a2 = strlen(word2);int** dp = calloc(a1+1,sizeof(int*));for(int i = 0;i <= a1;i++){dp[i] = calloc(a2+1,sizeof(int));}for(int i = 0;i <= a1;i++){dp[i][0] = i;}for(int j = 0;j <= a2;j++){dp[0][j] = j;}for(int i = 1;i <= a1;i++){for(int j = 1;j <= a2;j++){if(word1[i-1] == word2[j-1]){dp[i][j] = dp[i-1][j-1];}else{dp[i][j] = fmin(dp[i-1][j-1],fmin(dp[i-1][j],dp[i][j-1]))+1;}}}return dp[a1][a2];
}
反思
今天的难度还算适中，整体并不难，但是有些题目你不看解析想不到。
