算法|面试必刷算法TOP101之DP篇 TOP6 DP|动态规划|算法|动态规划

编辑距离题目来源：Leetcode
1、问题描述
给定两个字符串word1和word2，返回转换为所需的最少操作数word1word2。
您可以对单词进行以下三个操作：

插入一个字符
删除一个字符
替换一个字符

【算法|面试必刷算法TOP101之DP篇 TOP6】示例：

文章图片

2、思路分析

文章图片

文章图片

3、代码实现

class Solution { public: int minDistance(string word1, string word2) { int len1=word1.size(); int len2=word2.size(); vector> v(len1+1,vector(len2+1)); for(int i=0; i<=len1; i++) v[i][0]=i; for(int i=0; i<=len2; i++) v[0][i]=i; for(int i=1; i<=len1; i++){ for(int j=1; j<=len2; j++){ //在删除拆入选一个最小的 v[i][j]=min(v[i][j-1],v[i-1][j])+1; //最后一个字符相等就不需要替换字符 if(word1[i-1]==word2[j-1]){ //不需要操作，从v[i][j]也就是在删除，替换中选出最小的中和(i-1,j-1)选一个最小的 v[i][j]=min(v[i][j],v[i-1][j-1]); }else{ //需要替换字符 //需要操作，从v[i][j]也就是在删除，替换中选出最小的中和(i-1,j-1)+1加一也就是在前i-1次操作后还需要替换一次选一个最小的 v[i][j]=min(v[i][j],v[i-1][j-1]+1); } } }return v[len1][len2]; } };

不同的子序列题目来源：Leetcode
1、问题描述
给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。
字符串的一个子序列是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，“ACE” 是 “ABCDE” 的一个子序列，而 “AEC” 不是）
示例：

文章图片

2、思路解析

文章图片

文章图片

3、代码实现

class Solution { public: int numDistinct(string s, string t) { intlen1=s.size(); int len2=t.size(); vector> v(len1+1 ,vector(len2+1,0)); //T为空字符但是字串个数还是1 for(int i=0; i<=len1; i++){ v[i][0]=1; } for(int i=1; i<=len1; i++){ for(int j=1; j<=len2; j++){ if(s[i-1]==t[j-1]){ //相等使用第i个字符和不使用前i个字符 v[i][j]=v[i-1][j-1]+v[i-1][j]; }else{ //不相等退化为在s前i-1找T的前j个字符 v[i][j]=v[i-1][j]; } } } return v[len1][len2]; } };