day 48| 子序列问题

115.不同的子序列

如果当前 s 和 t遍历的索引分别是i和 j，

• 如果 i 和 j 不相同，则子序列个数是 dp[i-1][j] 因为求得是完整的 t 序列在 s 中的出现个数。
• 如果 i 和 j 相同，则子序列的个数就是dp[i-1][j-1]+dp[i-1][j] 应该是t[:j-1]在s[:i-1]的个数和t[:j]在s[:i-1]出现的个数之和。
• 需要注意的是初始化的过程。 整体遍历顺序是从上到下。所以需要初始化第一行。 同时注意 i-1的范围，所以要初始化第一列。
• 首先是 dp[0][0] 两个空字符串，应该相等。所以初始化为 1
• 第一列表示的是空字符在 s 中出现的个数。 s 中没有任何空字符串走表达式dp[i-1][j] 均为 1
• 第一行表示的是t 的子串在 空字符串出现的个数。显然均为 0
• 然后试着反推可以得到正确的结果

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

同样如果当前两个字符相等 则最小距离不变。如果不相等，则等于min(dp[i-1][j]+1,dp[i]j-1]+1)

初始化都变为空字符串所以dp[i][0]的值均等于索引

72. 编辑距离

和删除一样，只不过多了替换的操作。如果不相等，则等于min(dp[i-1][j]+1,dp[i]j-1]+1，dp[i-1][j-1]+1)