广州哪个公司做网站,做酒店网站设计,深圳市造价信息网官网,网站流量的作用动态规划day45:编辑距离|115. 不同的子序列、583. 两个字符串的删除操作、72. 编辑距离(动规终极好题#xff09; 115. 不同的子序列583. 两个字符串的删除操作72. 编辑距离(动规终极好题) 115. 不同的子序列
给你两个字符串 s 和 t #xff0c;统计并返回在 s 的 子序列 中… 动态规划day45:编辑距离|115. 不同的子序列、583. 两个字符串的删除操作、72. 编辑距离(动规终极好题 115. 不同的子序列583. 两个字符串的删除操作72. 编辑距离(动规终极好题) 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 由英文字母组成
class Solution {
public:int numDistinct(string s, string t) {vectorvectoruint64_t dp(s.size()1,vectoruint64_t(t.size()1));for(int i0;is.size();i)dp[i][0]1;for(int i1;it.size();i)dp[0][i]0;for(int i1;is.size();i)for(int j1;jt.size();j){if(s[i-1]t[j-1])dp[i][j]dp[i-1][j-1]dp[i-1][j];elsedp[i][j]dp[i-1][j];}return dp[s.size()][t.size()];}
};本题关键递推公式的推导
首先dp [i] [j]的含义是以 s[i-1] 为结尾的序列中有多少个以 t[j-1] 为结尾的序列。
据此我们分两种情况来讨论: 第一种当s[i-1]与t[j-1]不相等那么s有没有s[i-1]效果其实都是一样的即dp[i] [j]dp[i-1] [j]。 第二种当s[i-1]与t[j-1]相等时此时s[i-1]显然时有用的。当我们使用s[i-1]时由于末尾元素相等我们稍加思索可以得出dp[i] [j]dp[i-1] [j-1]当我们不使用s[i-1]时则和第一种一样d[i] [j]dp[i-1] [j]。那么它们是求和还是求最大值呢显然是求和了即 if(s[i-1]t[j-1])dp[i][j]dp[i-1][j-1]dp[i-1][j];elsedp[i][j]dp[i-1][j];另外uint64_t等效于unsigned long 且uint64_t 表示数据范围则是0 ~2^64-1int16_t 表示数据范围为-264~264-1。 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 只包含小写英文字母
class Solution {
public:int minDistance(string word1, string word2) {int len1word1.size();int len2word2.size();vectorvectorint dp(len11,vectorint(len21));for(int i0;ilen1;i)dp[i][0]i;for(int j1;jlen2;j)dp[0][j]j;for(int i1;ilen1;i)for(int j1;jlen2;j){if(word1[i-1]word2[j-1])dp[i][j]dp[i-1][j-1];elsedp[i][j]min(dp[i-1][j]1,dp[i][j-1]1);}return dp[len1][len2];}
};在上一题的基础上这道题还是很容易想出来的。递推公式的逻辑是当末尾元素相等时就等效于把末尾元素去掉即dp[i] [j]dp[i-1] [j-1]当末尾元素不相等时那么末尾元素必要删一个分两种情况然后取最小值即可。
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 由小写英文字母组成
class Solution {
public:int minDistance(string word1, string word2) {int len1word1.size();int len2word2.size();vectorvectorint dp(len11,vectorint(len21));for(int i0;ilen1;i)dp[i][0]i;for(int j1;jlen2;j)dp[0][j]j;for(int i1;ilen1;i)for(int j1;jlen2;j){if(word1[i-1]word2[j-1])dp[i][j]dp[i-1][j-1];elsedp[i][j]min(min(dp[i-1][j]1,dp[i][j-1]1),dp[i-1][j-1]1);}return dp[len1][len2];}
};难点还是在递归公式要分两种情况讨论
当word1[i-1]word2[j-1]时此时末尾元素相等说明这两个元素时不需要操作的则dp [i] [j]dp [i-1] [j-1]当word1[i-1]!word2[j-1]时又要分3种情况讨论 删若删 word1则dp [i] [j]dp [i-1] [j]1若删 word2则dp [i] [j]dp [i] [j-1]1增从问题的本质上讲增和删时一致的即 word2 增其实是等效于 word1 删。也就是说实现增和删效果的代码本质上是一致的所以不用另写替换两个末尾元素都参与替换了显然dp [i] [j]dp [i-1] [j-1]1
