11.29 代码随想录Day45打卡(动态规划)

发布于:2024-11-29 ⋅ 阅读:(35) ⋅ 点赞:(0)

115.不同的子序列

题目:给你两个字符串 s 和 t ,统计并返回在 s 的 子序列 中 t 出现的个数。

题解:

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]
        for i in range(len(s)):
            dp[i][0] = 1
        for j in range(1, len(t)):
            dp[0][j] = 0
        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. 两个字符串的删除操作

题目:给定两个单词 word1 和 word2 ,返回使得 word1 和  word2 相同所需的最小步数每步 可以删除任意一个字符串中的一个字符。

题解:

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][j-1]+1, dp[i-1][j-1]+2)
        return dp[-1][-1]

72. 编辑距离

题目:给两个单词 word1 和 word2, 请返回将 word1 转换成 word2 所使用的最少操作数  。你可以对一个单词进行如下三种操作:插入一个字符,删除一个字符,替换一个字符。

题解:

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][j-1]+1, dp[i-1][j-1]+1)
        return dp[-1][-1]


网站公告

今日签到

点亮在社区的每一天
去签到