动态规划之编辑距离总结篇体会到carl的用心良苦

392.判断子序列

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

这道题可以用双指针也可以用动规，关于动规：

当s[i - 1] 与 t[j - 1]相等时，  dp[i][j]=dp[i-1][j-1]+1;

当s[i-1]和t[j-1]不相等时，相当于t要删除元素，继续匹配，所以dp[i][j]=dp[i][[j-1]

115.不同的子序列

给定一个字符串 s 和一个字符串 t ，统计并返回在 s 的 子序列 中 t 出现的个数，本题也只有删除操作，不用考虑替换增加之类.

那么当s[i - 1] 与 t[j - 1]相等时，dp[i][j]可以有两部分组成。一部分是由s[i-1]来匹配，那么个数为dp[i-1][j-1];一部分是不用s[i-1]来匹配，个数为dp[i-1][j]。如s="bagg",t="bag"。所以当s[i-1]和t[j-1]相等时，dp[i][j]=dp[i-1][j-1]+dp[i-1][j];

当s[i-1]和t[j-1]不相等时，dp[i][j]只有一部分组成，不用s[i-1]来匹配，即dp[i][j]=dp[i-1][j](相当于删除掉s要删除元素，不知道这样理解对不对)

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

有word1和word2，可以分别对二者进行删除操作，

这道题当word1[i-1]==word2[j-1]的时候递推公式很好理解，dp[i][j]=dp[i-1][j-1]

但是当word1[i-1]！=word2[j-1]时候，我们可以对word1删除或者对word2删除，即dp[i][j]=min(dp[i][j-1],dp[i-1][j])+1

72.编辑距离

有word1和word2，可以分别对二者进行增，删，替换操作

这道题当word1[i-1]==word2[j-1]的时候递推公式很好理解，dp[i][j]=dp[i-1][j-1]

但是当word1[i-1]！=word2[j-1]时候，我们原本是有对word1增加，对word2增加，对word1删除，对word2删除，对word1替换，对word2替换操作的，经过一通分析本质上只有对word1删除，对word2删除，对word1替换三种操作即dp[i][j]=min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])+1