115、不同的子序列://dp[i][j]:以i-1结尾的字符串s中有多少个以j-1结尾的字符串t //递推公式:删除s中的字符以匹配t。 //两元素相等时,可以考虑在s中使用该元素,或者不使用该元素。 //if(s[i-1] == t[j-1]) dp[i][j] = dp[i-1][j-1] + dp[i-1][j]; //else dp[i][j] = dp[i-1][j]; //初始化:dp[i][0](t为空字符串)初始化为1,dp[0][j](s为空字符串)初始化为0583、两个字符串的删除操作,使得word1与word2相同//两个字符串的删除操作,就相当于找到两个字符串的最长公共子序列 //dp[i][j]:长度[0,i-1]的s1和长度[0,j-1]的s2的最长公共子序列的长度72、编辑距离//要将word1转换为word2难点是当两个元素不相等时,分别取增删替操作中最小的 //dp[i][j]:以i-1结尾的word1转换成以j-1结尾的word2最小编辑次数 //递推公式:主要分为相等和不相等两种情况的操作 //if(word1[i-1] == word2[j-1]) dp[i][j] = dp[i-1][j-1]; //else dp[i][j] = min(dp[i-1][j] + 1,//word1删除当前字符 // min(dp[i-1][j-1] + 1,//word1替换当前字符 // dp[i][j-1] + 1))//word1插入一个字符 //初始化:dp[i][0](word2为空字符,所以要删掉所有word1的元素)初始化为i //dp[0][j](word1为空字符,所以要插入所有word2的元素)初始化为j