代码随想录算法训练营day50|动态规划12

差别的子序列

给定一个字符串 s 和一个字符串 t ，盘算在 s 的子序列中 t 出现的个数。、
编辑间隔中的删除元素，实在就是直接变数字，其只删除原来的较长的数组里的元素

递推模拟，利用s的末了一个元素匹配，大概删除末了一个元素看前面一个是否匹配

初始化，dp[0]=1体现s不为空，t为空，如许把s删到空就肯定有一个，同理dp[0]=0,重叠部门dp[0][0]就即是空字符串匹配空字符串，为1

界说为int，出现了超时错误

以是可以用longlongint 的别名 uint64_t

1. class Solution {
2. public:
3.     int numDistinct(string s, string t) {
4.         vector<vector<uint64_t>> dp(s.size()+1,vector<uint64_t>(t.size()+1));
5.         for(int i=0;i<s.size();i++) dp[i][0]=1;
6.         for(int j=1;j<t.size();j++) dp[0][j]=0;
7.         for(int i=1;i<=s.size();i++){
8.             for(int j=1;j<=t.size();j++){
9.                 if(s[i-1]==t[j-1]){
10.                     dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
11.                 }
12.                 else{
13.                     dp[i][j]=dp[i-1][j];
14.                 }
15.             }
16.         }
17.         return dp[s.size()][t.size()];
18.     }
19. };

复制代码

两个字符串的删除利用

实在就是两个字符串都可以删除了
递推公式如下

1. class Solution {
2. public:
3.     int minDistance(string word1, string word2) {
4.         vector<vector<int>> dp(word1.size()+1,vector<int>(word2.size()+1));
5.         for(int i=0;i<=word1.size();i++) dp[i][0]=i;
6.         for(int j=0;j<=word2.size();j++) dp[0][j]=j;
7.         for(int i=1;i<=word1.size();i++){
8.             for(int j=1;j<=word2.size();j++){
9.                 if(word1[i-1]==word2[j-1]) dp[i][j]=dp[i-1][j-1];
10.                 else dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1);
11.             }
12.         }
13.         return dp[word1.size()][word2.size()];
14.     }
15. };

复制代码

思绪二是，先求出公共子序列的长度，再用两个字符串的总长度减去公共子序列的长度

1. class Solution {
2. public:
3.     int minDistance(string word1, string word2) {
4.         vector<vector<int>> dp(word1.size()+1, vector<int>(word2.size()+1, 0));
5.         for (int i=1; i<=word1.size(); i++){
6.             for (int j=1; j<=word2.size(); j++){
7.                 if (word1[i-1] == word2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
8.                 else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
9.             }
10.         }
11.         return word1.size()+word2.size()-dp[word1.size()][word2.size()]*2;
12.     }
13. };

复制代码

编辑间隔（动规经典标题）

=为什么这道题不能接纳上一题的思绪二，先求出公共子序列的长度，再用两个字符串的总长度减去公共子序列的长度，由于很大概长度一样，但可以只更换一次就完成，但思绪2会要求按着序次删除