如何才能做好品牌网站建设策划,网站源码系统,公司汇报网站建设方案,在网站和网页的区别判断子序列[https://leetcode.cn/problems/is-subsequence/description/] 题意#xff1a;给定字符串 s 和 t #xff0c;判断 s 是否为 t 的子序列。 思路#xff1a;从动态规划#xff0c; dp[i][j] 表示s的前i-1个元素和t的前j-1个元素相同的子序列元素的个数。 还要对d…判断子序列[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 。 因为有这样的例子 sbagg 和 tbag 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 1e310 ;// 可以映射为删除s的元素的方式使得s最后与t相等的个数vectorvectoruint64_t dp(s.size()10 , vectoruint64_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 i1 ; 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){coutdp[i][j] ; }coutendl ; }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) {vectorvectoruint64_t dp(word1.size()10, vectoruint64_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 ; // 步数是i1 删除i个字符串。 可以达到word2为空的状态。 }for(int j 0 ; j word2.size() ; j){dp[0][j] j ; // 步数是j1 ; 删除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()] ;
