leetcode刷题-动态规划12

115.不同的子序列 – 递推公式略难理解

leetcode题目链接
代码随想录文档讲解

思路：

s中有多少种删除字符串的方式使之变为t

1. dp数组定义，dp[i][j]: (i-1) 为结尾的s与 j-1为结尾的t的个数

2. 递推公式
   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-1][j]，不是j-1
   如果两个元素相等，可以使用这个元素也可以不使用s中的这个元素
   如果不相同，就要删除s中这个元素再进行计算
   

3. 初始化： dp[i][0] = 1（s不空，t为空）, dp[0][j] = 0 （s为空），dp[0][0] = 1

4. 遍历顺序
   从左到右，从上到下

python代码：

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        if len(s) < len(t):
            return 0
        dp = [[0]*(len(t)+1) for _ in range(len(s)+1)]
        for i in range(len(s)+1):
            dp[i][0] = 1
        for i in range(1, len(s)+1):
            for j in range(1, len(t)+1):
                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]
        return dp[-1][-1]   

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

leetcode题目链接
代码随想录文档讲解

思路：

本题递推公式较为好像，但第一次提交初始化出错未通过
初始化注意：dp[i][0] = i；dp[0][j] = j

python代码：

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        dp = [[0]*(len(word2)+1) for _ in range(len(word1)+1)]
        for i in range(len(word1)+1):
            dp[i][0] = i
        for j in range(len(word2)+1):
            dp[0][j] = j
        for i in range(1, len(word1)+1):
            for j in range(1, len(word2)+1):
                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]+2, dp[i-1][j]+1, dp[i][j-1]+1)
        return dp[-1][-1]

class Solution(object):
    def minDistance(self, word1, word2):
        m, n = len(word1), len(word2)
        
        # dp 求解两字符串最长公共子序列
        dp = [[0] * (n+1) for _ in range(m+1)]
        for i in range(1, m+1):
            for j in range(1, n+1):
                if word1[i-1] == word2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
                    
        # 删去最长公共子序列以外元素
        return m + n - 2 * dp[-1][-1]

72. 编辑距离

leetcode题目链接
代码随想录文档讲解

思路：

1. dp数组定义
   dp[i][j] 以i-1为结尾的word1和以j-1为结尾的word2最少操作次数

2. 递推公式
   两种情况：if dp[i-1] == dp[j-1]: dp[i][j] = dp[i-1][j-1] 不需要修改元素
   else: dp[i][j] = min(dp[i-1][j] +1, dp[i][j-1]+1, dp[i-1][j-1]+1) (删除元素和添加元素是逆向操作，操作次数一致，只需要考虑一种即可）（替换一个元素，使word1中这个元素和word2中这个元素相同）

3. 初始化
   dp[i][0] = i 和 dp[0][j] = j 注意

4. 遍历顺序
   从前往后，从左往右

python代码：

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        dp = [[0]*(len(word2)+1) for _ in range(len(word1)+1)]
        for i in range(len(word1)+1):
            dp[i][0] = i
        for j in range(len(word2)+1):
            dp[0][j] = j
        for i in range(1, len(word1)+1):
            for j in range(1, len(word2)+1):
                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], dp[i-1][j], dp[i][j-1]) + 1
        return dp[-1][-1]  

编辑距离总结篇

代码随想录文档讲解