定制网站型网站开发_广告设计策划公司_站长工具网址是多少_广告公司收费价格表

1.不同的子序列

1.1 题目

. - 力扣（LeetCode）

1.2 题解

class Solution {
public:int numDistinct(string s, string t) {//确定dp数组，dp[i][j]表示以i结尾的s和以j-1结尾的t，t在s中出现的次数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() + 1; i++){dp[i][0] = 1;}for (int j = 1; j < t.size() + 1; 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()];}
};

2.两个字符串的删除操作

2.1 题目

. - 力扣（LeetCode）

2.2 题解

class Solution {
public:int minDistance(string word1, string word2) {//确定dp数组,dp[i][j]表示以i-1结尾的word1和以j-1结尾的word2，最小步数vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size()+1,0));//确定递推逻辑      //初始化dp[0][0] = 0;for (int i = 1; i <= word1.size(); i++){dp[i][0] = i;}for (int j = 1; 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{dp[i][j] = min(min(dp[i - 1][j] + 1, dp[i][j - 1] + 1), dp[i - 1][j - 1] + 2);}}}return dp[word1.size()][word2.size()];}
};

3.编辑距离

3.1 题目

. - 力扣（LeetCode）

3.2 题解

class Solution {
public:int minDistance(string word1, string word2){//确定dp数组，dp[i][j]表示以i-1J结尾的word1转换为以j-1结尾的word2vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1));//确定递推公式//初始化dp[0][0] = 0;for (int i = 1; i <= word1.size(); i++){dp[i][0] = i;}for (int j = 1; 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{//增和删int a = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);//换int b = dp[i - 1][j - 1] + 1;dp[i][j] = min(a, b);}}}return dp[word1.size()][word2.size()];}
};