今日收获：不同的子序列，两个字符串的删除操作，编辑距离

1. 不同的子序列

题目链接：115. 不同的子序列 - 力扣（LeetCode）

思路：

（1）dp数组表示两个字符串 i-1,j-1位置之前的相同子序列个数。

（2）初始化：如果s不为空串，t为空串，那么dp数组值为1；反之dp数组值全为0

（3）遍历顺序：当前位置的值取决于左上角元素和上方元素，所以是从上到下从左到右遍历

（4）递推公式：如果当前位置的字符相等，那么值就等于两个字符串都向前移一位的值+大字符串向前移一位的值；如果不相等，当前位置的值大字符串向前移一位的值，看看s中前面的字符匹配了多少个t

方法：

java">class Solution {public int numDistinct(String s, String t) {int len1=s.length();int len2=t.length();int[][] dp=new int[len1+1][len2+1];// 初始化，字符串中有一个空串for (int i=0;i<len1+1;i++){dp[i][0]=1;}for (int j=1;j<len2+1;j++){  // 空字符串中没有tdp[0][j]=0;}for(int i=1;i<=len1;i++){for (int j=1;j<=len2;j++){if (s.charAt(i-1)==t.charAt(j-1)){dp[i][j]=dp[i-1][j-1]+dp[i-1][j];}else {dp[i][j]=dp[i-1][j];}}}return dp[len1][len2];}
}

2. 两个字符串的删除操作

题目链接：583. 两个字符串的删除操作 - 力扣（LeetCode）

思路：两个单词都可以删除。如果两个单词当前位置的字符不相等，一共有三种删除情况取最小值。

方法：

java">class Solution {public int minDistance(String word1, String word2) {int len1=word1.length();int len2=word2.length();int[][] dp=new int[len1+1][len2+1];// 初始化dp[0][0]=0;for (int i=1;i<len1+1;i++){dp[i][0]=i;}for (int j=1;j<len2+1;j++){dp[0][j]=j;}for (int i=1;i<len1+1;i++){for (int j=1;j<len2+1;j++){if (word1.charAt(i-1)==word2.charAt(j-1)){dp[i][j]=dp[i-1][j-1];}else {dp[i][j]=Math.min(Math.min(dp[i][j-1]+1,dp[i-1][j]+1),dp[i-1][j-1]+2);}}}return dp[len1][len2];}
}

3. 编辑距离

题目链接：72. 编辑距离 - 力扣（LeetCode）

思路：当字符串不匹配时，dp[i-1][j]+1,dp[i][j-1]+1代表分别对两个字符串进行删除（增加）的操作；dp[i-1][j-1]+1表示替换操作。

方法：

java">class Solution {public int minDistance(String word1, String word2) {int len1=word1.length();int len2=word2.length();int[][] dp=new int[len1+1][len2+1];// 初始化for (int i=0;i<len1+1;i++){dp[i][0]=i;}for (int j=1;j<len2+1;j++){dp[0][j]=j;}for (int i=1;i<len1+1;i++){for (int j=1;j<len2+1;j++){if (word1.charAt(i-1)==word2.charAt(j-1)){dp[i][j]=dp[i-1][j-1];}else {dp[i][j]=Math.min(Math.min(dp[i-1][j]+1,dp[i][j-1]+1),dp[i-1][j-1]+1);}}}return dp[len1][len2];}
}