Day59 动态规划part12

LC115不同的子序列（未掌握）

1. 递推公式与LC392类似，但是初始化略有不同

• LC392的dp数组含义为相同字符个数
• 而本体的dp数组含义为出现的次数，因此dp[i][0]=1

2. 两种情况

• s[i-1]==t[j-1]
  • dp[i][j] = dp[i-1][j-1]
  • dp[i][j] = dp[i-1][j]
• s[i-1]!=t[j-1]=》dp[i][j] = dp[i-1][j]

3. 代码
   

LC583两个字符串的删除操作

1. 其实本质就是求最长公共子序列，跟LC1143一样
2. 代码
   
3. 方法二：

• dp[i][j]：以i-1为结尾的字符串word1，和以j-1位结尾的字符串word2，想要达到相等，所需要删除元素的最少次数。
• 递推公式：
  • 当word1[i - 1] == word2[j - 1]：dp[i][j] = dp[i - 1][j - 1];
  • 当word1[i - 1] ！= word2[j - 1]
    • 删word1[i - 1]，最少操作次数为dp[i - 1][j] + 1
    • 删word2[j - 1]，最少操作次数为dp[i][j - 1] + 1
    • 同时删word1[i - 1]和word2[j - 1]，操作的最少次数为dp[i - 1][j - 1] + 2
    • 但是dp[i][j - 1] + 1 = dp[i - 1][j - 1] + 2，当 同时删word1[i - 1]和word2[j - 1]，dp[i][j-1] 本来就不考虑 word2[j - 1]了，那么我在删 word1[i - 1]，是不是就达到两个元素都删除的效果，即 dp[i][j-1] + 1
• 代码
  

LC72 编辑距离（未掌握）

1. dp[i][j] 表示以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2，最近编辑距离为dp[i][j]。
2. 递推公式：
   • 当word1[i - 1] == word2[j - 1]：dp[i][j] = dp[i - 1][j - 1];
   • 当word1[i - 1] ！= word2[j - 1]
     • 删除word1[i - 1]=》dp[i][j] = dp[i - 1][j] + 1;
     • 删除word2[j - 1]=》dp[i][j] = dp[i ][j-1] + 1;
     • 增加：因为增加可以任意增加一个元素，增加元素就类似与删除元素，长为x和长为y的比较，如果需要增加一定是一个比另外一个长，那可以加一个也就可以用减一个元素替代
     • 替换：将word1[i - 1]替换为word2[j- 1]=》dp[i][j] = dp[i - 1][j - 1]+1;
3. 代码