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

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]
1
2
3
4
5
6
7
8
9
10
11
12
13
14

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

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]
1
2
3
4
5
6
7
8
9
10
11
12
13
14

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
1
2
3
4
5
6
7
8
9

再试试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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

关键在于遍历顺序和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
1
2
3
4
5
6
7
8
9
10
11
12
13
14