2020-2-26 刷题记录

2 月份的刷题数量,比预期要少 15 道左右,dp 难度是挺大的,今天只做了三道,上半年目标是 450 道,加油

0X00 leetcode 刷题 3 道

• leetcode 518. Coin Change 2
• leetcode 474. Ones and Zeroes
• leetcode 516. Longest Palindromic Subsequence

0X01 每道题的小小总结

518. Coin Change 2

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        # 这是一个背包问题
        # 做法不能是 f(x) = f(x-1) + f(x-2) + f(x-5)
        # 这样会出现重复的问题
        # 而是
        # 用 1 可以有多少种解法
        # 用 1 和 2 可以有多少种解法
        # 用 1 和 2 和 5 可以有多少种解法
        
        dp = [0] * (amount + 1)
        # 当没有 amount 的时候可以用 0 个硬币的方法
        # 所以是 1
        dp[0] = 1

        for c in coins:
            for x in range(c, amount+1):
                dp[x] += dp[x-c]
        
        return dp[amount]

看看「官方题解」还是很不错的,做法就是

• 用硬币 1 每个数字有几种解法
• 用硬币 1 2 每个数字有几种解法
• 用硬币 1 2 5 每个数字有几种解法
• ....

474. Ones and Zeroes

这也是「背包问题」两个背包的问题

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        # 用动态规划做这个题
        # dp(i, j) 代表用 i 个 0 j 个 1 能组成多少个字符串
        # 所以写出 转移方程 dp(i, j) = max(dp(i-cost_zeros[k], j - cost_ones[k]) + 1, dp(i, j))
        # 每个字符串只能使用一次,我们遍历的时候要选择从后往前遍历,否则会重复计算当前字符串
        N = len(strs)
        dp, cost = [[0 for _ in range(n+1)] for _ in range(m+1)], [[0] * 2 for _ in range(N)]

        # 计算每个 str 用了多少个 0 和 1
        for i in range(N):
            cost[i][0] = strs[i].count("0")
            cost[i][1] = strs[i].count("1")
        
        for i in range(N):
            cost_zeros, cost_ones = cost[i][0], cost[i][1]
            for x in range(m, -1, -1):
                for y in range(n, -1, -1):
                    if cost_zeros <= x and cost_ones <= y:
                        dp[x][y] = max(dp[x - cost_zeros][y-cost_ones] + 1, dp[x][y])             
                        
        
        
        return dp[m][n]

有一个 trick 是:必须从后往前更新,否则会重复计算当前字符串

516. Longest Palindromic Subsequence

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        # 动态规划去做这个题目
        # 区间型动态规划
        # f(i, j) = max(f(i, j-1), f(i+1, j), f(i+1, j-1) + 2 | s[i] == s[j])
        # i,j 是下标
        # 按长度去做
        # 提交之前想想有没有漏掉的东西
        if len(s) == 0: return 0
        m = len(s)
        dp = [[0 for _ in range(m+1)] for _ in range(m)]
        
        # len 1
        for x in range(m):
            dp[x][x] = 1
        
        # len 2
        for x in range(m-1):
            dp[x][x+1] = 2 if s[x] == s[x+1] else 1
        
        for l in range(3, m+1):
            for x in range(m-l+1):
                y = x + l - 1
                dp[x][y] = max(dp[x+1][y], dp[x][y-1])
                if s[x] == s[y]:
                    dp[x][y] = max(dp[x][y], dp[x+1][y-1] + 2)
        
        return dp[0][m-1]

这个题有一个特别的地方,它是靠长度去遍历的「区间型」动态规划