代码随想录训练营第45天|编辑距离
115. 不同的子序列
class Solution {
public:int numDistinct(string s, string t) {s.insert(s.begin(),' ');t.insert(t.begin(),' ');int ns=s.length();int nt=t.length();vector<vector<uint64_t>> dp(ns,vector<uint64_t>(nt,0));for(int i=0; i<ns; i++){dp[i][0]=1;}for(int i=1; i<ns; i++){for(int j=1; j<nt; j++){if(s[i]==t[j])dp[i][j]=dp[i-1][j-1]+dp[i-1][j];elsedp[i][j]=dp[i-1][j];}}return dp[ns-1][nt-1];}
};dp[i][j]:截止到s[i],t[j]（包含）的两个子串所形成的子序列个数。
转移方程：
1.若结尾不等，则s[i]无法发挥作用，只能由i-1前的子串构建，个数等同于dp[i-1][j]
2.若结尾相等，则有两种选择：
- s[i]参与构建，则s的i-1前的子串要负责构建t的j-1部分的序列，个数为dp[i-1][j-1]
- s[i]不参与构建，则s的i-1前的子串要负责构建全部t的序列，个数为dp[i-1][j]
583. 两个字符串的删除操作
class Solution {
public:int minDistance(string word1, string word2) {word1.insert(word1.begin(),' ');word2.insert(word2.begin(),' ');int n1=word1.length(), n2=word2.length();vector<vector<int>> dp(n1,vector<int>(n2,0));for(int j=1; j<n2; j++){dp[0][j]=j;}for(int i=1; i<n1; i++)dp[i][0]=i;for(int i=1; i<n1; i++){for(int j=1; j<n2; j++){if(word1[i]==word2[j])dp[i][j]=dp[i-1][j-1];elsedp[i][j]=min(dp[i-1][j],dp[i][j-1])+1;}}return dp[n1-1][n2-1];}
};dp[i][j]:由word1[0:i]到word2[0:j]的最小删除操作数目
转移方程：
1.若结尾相等，则不会增加操作数，由dp[i-1][j-1]转移而来
2.若结尾不等，则有两种可能：
- 删除word1的结尾，由dp[i-1][j]转移而来
- 删除word2的结尾，由dp[i][j-1]转移而来
取二者较小。
72. 编辑距离
class Solution {
public:int minDistance(string word1, string word2) {word1.insert(word1.begin(),' ');word2.insert(word2.begin(),' ');int n1=word1.length(), n2=word2.length();vector<vector<int>> dp(n1,vector<int>(n2,0));for(int j=1; j<n2; j++)dp[0][j]=j;for(int i=1; i<n1; i++)dp[i][0]=i;for(int i=1; i<n1; i++){for(int j=1; j<n2; j++){if(word1[i]==word2[j])dp[i][j]=dp[i-1][j-1];elsedp[i][j]=min({dp[i-1][j],dp[i][j-1],dp[i-1][j-1]})+1;}}return dp[n1-1][n2-1];}
};dp[i][j]:由word1[0:i]到word2[0:j]的编辑距离
转移方程：
1.若结尾相等，则不会增加编辑距离，由dp[i-1][j-1]转移而来
2.若结尾不等，则有三种可能：
- 删除word1的结尾，由dp[i-1][j]转移而来
- 删除word2的结尾，由dp[i][j-1]转移而来
- 修改word1与word2的最后一位，由dp[i-1][j-1]转移而来。
取三者较小。