LeetCode|动态规划|392. 判断子序列、115. 不同的子序列、 583. 两个字符串的删除操作
目录
一、392. 判断子序列
1.题目描述
2.解题思路
3.代码实现(双指针解法)
4.代码实现（动态规划解法）
二、115. 不同的子序列
1.题目描述
2.解题思路
3.代码实现（C语言版本）
4.代码实现（C++版本）
三、583. 两个字符串的删除操作
1.题目描述
2.解题思路
3.代码实现（C语言版本）
一、392. 判断子序列
1.题目描述
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
示例 1：
输入：s = "abc", t = "ahbgdc" 输出：true
示例 2：
输入：s = "axc", t = "ahbgdc" 输出：false
提示：
0 <= s.length <= 1000 <= t.length <= 10^4- 两个字符串都只由小写字符组成。
2.解题思路
1.双指针解法：这也是看到这个题目一开始想到的方法
- 指针p1指向s开头，指针p2指向t开头，分别判断是否相等，相等就p1++,p2++,否则就p2++
2.动态规划解法：判断这两个字符串数组，最长公共子序列长度是否==s.szie()
3.代码实现(双指针解法)
bool isSubsequence(char* s, char* t) {char* p1 = s;char* p2 = t;for(;*p1!='\0',*p2!='\0';){if(*p1==*p2){p1++;p2++;}else {p2++;}}if(*p1 == '\0')return true;return false;
}4.代码实现（动态规划解法）
bool isSubsequence(char* s, char* t) {//考虑用最长公共子序列求解//动态规划思路，如果最长公共子序列的长度是字符串s的长度，那么就return trueint slen = strlen(s);int tlen = strlen(t);//对于dp数组初始化int **dp = (int**)malloc(sizeof(int*)*(slen+1));for(int i = 0;i <= slen;i++){dp[i] = (int*)malloc(sizeof(int) * (tlen+1));for(int j = 0;j <= tlen;j++){dp[i][j] = 0;}}for(int i = 1;i <= slen;i++){for(int j = 1;j<=tlen;j++){if(s[i-1]==t[j-1]){dp[i][j] = dp[i-1][j-1]+1;}else{dp[i][j] = dp[i][j-1];}}}int result = dp[slen][tlen];for(int i = 0;i <= slen;i++){free(dp[i]);}free(dp);if(result == slen) return true;else return false;
}二、115. 不同的子序列
1.题目描述
给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 109 + 7 取模。
示例 1：
输入：s = "rabbbit", t = "rabbit"输出：3解释： 如下所示, 有 3 种可以从 s 中得到"rabbit" 的方案。rabbbitrabbbitrabbbit
示例 2：
输入：s = "babgbag", t = "bag"输出：5解释： 如下所示, 有 5 种可以从 s 中得到"bag" 的方案。babgbagbabgbagbabgbagbabgbagbabgbag
2.解题思路
- 动态规划解法，dp数组含义：以i-1结尾的s中，含有以j-1结尾的t的个数为dp[i][j]
3.代码实现（C语言版本）
int numDistinct(char* s, char* t) {int slen = strlen(s);int tlen = strlen(t);//dp数组含义：以i-1结尾的s中 有 以j-1结尾的t 的个数为dp[i][j]uint64_t** dp = (uint64_t**)malloc(sizeof(uint64_t*) * (slen+1));for(int i = 0; i <= slen;i++){dp[i] = (uint64_t*)malloc(sizeof(uint64_t)* (tlen+1));}//dp初始化:第一列初始化为1，第一行初始化为0for(int j = 1;j <= tlen;j++){dp[0][j] = 0;}for(int i = 0;i <= slen;i++){dp[i][0] = 1;}for(int i = 1;i <= slen;i++){for(int j = 1;j <= tlen;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];}}}uint64_t result = dp[slen][tlen];//打印dp数组for(int i = 0;i <= slen;i++){for(int j = 0;j <= tlen;j++){printf("%d ",dp[i][j]);}}for(int i = 0;i < slen;i++){free(dp[i]);}free(dp);return result;}4.代码实现（C++版本）
class Solution {
public:int numDistinct(string s, string t) {vector<vector<uint64_t>> dp(s.size() + 1, vector<uint64_t>(t.size() + 1));for (int i = 0; i < s.size(); i++) dp[i][0] = 1;for (int j = 1; j < t.size(); j++) dp[0][j] = 0;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. 两个字符串的删除操作
1.题目描述
给定两个单词 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只包含小写英文字母
2.解题思路
- 动态规划思路
- 最长公共子序列思路：求出最长公共子序列长度，然后计算这两个字符串长度之和，减去2倍的最长公共子序列，就是我们要求的答案。
3.代码实现（C语言版本）
//min函数
int min(int a,int b){return a>b?b:a;
}int minDistance(char* word1, char* word2) {int len1 = strlen(word1);int len2 = strlen(word2);//dp数组含义：以下标i-1结尾的word1，j-1结尾的word2，使它们相等最小步数为dp[i][j]//初始化二维数组dp,第一行和第一列需要单独初始化，分别表是word1为空，word2以下标j结尾此时移动多少步相等，显然是j步int** dp = (int**)malloc(sizeof(int*)*(len1+1));for(int i = 0;i <= len1;i++){dp[i] = (int*)malloc(sizeof(int) * (len2+1));for(int j = 0;j <= len2;j++){dp[i][j] = 0;}}for(int i = 0;i <= len1;i++){dp[i][0] = i;}for(int j = 0; j <= len2;j++){dp[0][j] = j;}//开始遍历for(int i = 1;i <= len1;i++){for(int j = 1;j <= len2;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));}}}int result = dp[len1][len2];//freefor(int i = 0;i <= len1;i++){free(dp[i]);}free(dp);return result;
}