代码随想录 | 动态规划 part16 part17

发布于:2023-09-14 ⋅ 阅读:(85) ⋅ 点赞:(0)

583 两个字符串的删除操作

二维dp数组表示使得0-i和0-j字符串相同所需的最少操作步数
通过算例分析dp数组的推导公式写出来了

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 i in range(len(word2)+1):
            dp[0][i] = i
        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)
        return dp[-1][-1]

看解答发现不相等时其实有三种情况,不过递推公式可简化为两种

72 编辑距离

dp数组表示0-i和0-j的字符串转换为相同所需最少步数
相同时还是步数不变
不同时的操作有三种
增加,删除,替换
增加和删除本质是一样的,和前面一致
替换有区别,替换可以直接修改dpi-1j-1,通过一次操作变成dpij

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 i in range(len(word2)+1):
            dp[0][i] = i
        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]

647 回文子串

好像可以暴力遍历?
必须On^2时间复杂度,估计会超时。。
直接使用切片判断,居然没超时

class Solution:
    def countSubstrings(self, s: str) -> int:
        res = 0
        print(s[0:0])
        for i in range(len(s)):
            for j in range(i+1,len(s)+1):
                if s[i:j] == s[i:j][::-1]:
                    res += 1
        return res

再试试dp思路,
dp表示0-i字符串中回文子串的数目
递推?二维dp表示ij之间子串是否为回文子串,最后对dp数组求和
看了解答。发现dp数组定义没问题,不过循环和递推公式写不出来,并且暴力法实际上是On^3的,不过python利用切片一定程度上降低了复杂度,这可能是没有超时的原因

class Solution:
    def countSubstrings(self, s: str) -> int:
        dp = [[0]*len(s) for _ in range(len(s))]
        res = 0
        for i in range(len(s)-1,-1,-1):
            for j in range(i,len(s)):
                if s[i] == s[j]:
                    if j-i <= 1:
                        dp[i][j] = 1
                        res += 1
                    else:
                        if dp[i+1][j-1] == 1:
                            dp[i][j] = 1
                            res += 1
        return res

关键在于遍历顺序和dp可以从哪个状态推导得到

516 最长回文子序列

按照前面一题的逻辑,只能找到最长回文子串,也就是说字串是连续的,但子序列并非如此
基本逻辑不变,如果ij字符相等,则判断中间是否回文,如果回文则延长后也是回文
但如果ij不相等,此时也有可能构成回文子序列,只要把ij都删掉即可?
不对,看了解答发现dp数组定义变了,直接定义为ij之间最长回文子序列长度即可,只要ij相等即可+2
还是没考虑全,当ij不相等的时候,得看把左边右边加上去,哪一边有更长的最长回文子序列,而不能粗暴地把ij两端都删掉

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        dp = [[0]*len(s) for _ in range(len(s))]
        res = 1
        for i in range(len(s)-1,-1,-1):
            for j in range(i,len(s)):
                if i == j:
                    dp[i][j] = 1
                elif s[i] == s[j]:
                    dp[i][j] = dp[i+1][j-1] + 2
                else:
                    dp[i][j] = max(dp[i+1][j],dp[i][j-1])
                res = max(dp[i][j],res)
        return res

网站公告

今日签到

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