【基础算法精讲-学习记录】动态规划1

视频学习记录

https://www.bilibili.com/video/BV1Xj411K7oF/?

• 学习了之前的 【基础算法精讲-学习记录】回溯1, 【基础算法精讲-学习记录】回溯2和【基础算法精讲-学习记录】回溯3后，其实动态规划就是复用计算状态的回溯。

• 所以想写出动态规划，可以用记忆化搜索，递推和空间优化递推来逐步实现动态规划题目，具体可看下面代码记录。

• 在Python下，可以用@cache装饰器让递归函数实现自己记录状态和服用状态。

例题和课后作业代码记录

198. 打家劫舍

https://leetcode.cn/problems/house-robber/description/

class Solution:
    def rob(self, nums: List[int]) -> int:
        # 空间优化
        # 由于每个状态只依赖前面两个，也就是算上当前状态就只要三个数字即可
        pre_left, pre_right = 0, 0
        for num in nums:
            pre_left, pre_right = pre_right, max(pre_right, pre_left+num)
        return pre_right

        # 递推
        # 每个状态都依赖前面的两个状态 f[i] = max(f[i-1], f[i-2]+num[i])
        n = len(nums)
        f = [0]*(n+2) # 加2是需要对于第一个就不用特殊处理了
        for i, num in enumerate(nums):
            f[i+2] = max(f[i+1], f[i]+num)
        return f[-1]

        # 记忆化搜索
        @cache
        def dfs(i:int): #在前i+1个房屋中偷取的最大值
            if i < 0:
                return 0 
            return max(dfs(i-1), dfs(i-2)+nums[i])
        return dfs(len(nums)-1)

70. 爬楼梯

https://leetcode.cn/problems/climbing-stairs/description/

class Solution:
    def climbStairs(self, n: int) -> int:
        # 优化空间的递推，f[i]=f[i-1]+f[i-2]
        l, r = 1, 1
        for _ in range(n-1):
            l, r = r, l+r 
        return r 

        # 记忆化搜索
        @cache
        def dfs(i:int)->int:
            if i <= 1: # 针对 0 或 1
                return 1 
            return dfs(i-2) + dfs(i-1)
        return dfs(n)

746. 使用最小花费爬楼梯

https://leetcode.cn/problems/min-cost-climbing-stairs/description/

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        # 空间优化 
        f0, f1 = 0, 0
        n = len(cost)
        for i in range(2, n+1):
            f0, f1 = f1, min(f0+cost[i-2], f1+cost[i-1])
        return f1 

        # 递推 f[i] = min(f[i-1]+cost[i-1], f[i-2]+cost[i-2])
        n = len(cost)
        f = [0]*(n+1)
        for i in range(2, n+1):
            f[i] = min(f[i-1]+cost[i-1], f[i-2]+cost[i-2])
        return f[-1]

        # 记忆化搜索
        n = len(cost)
        @cache
        def dfs(i:int)->int: # i 是爬完前i个台阶的最小花费
            if i <= 1:
                return 0
            return min(dfs(i-1)+cost[i-1], dfs(i-2)+cost[i-2])
        return dfs(n)

3693. 爬楼梯 II

class Solution:
    def climbStairs(self, n: int, costs: List[int]) -> int:
        # 空间优化
        f0 = 0
        f1 = 1+costs[0]
        if n == 1:
            return f1 
        f2 = min(f0+4, f1+1)+costs[1]
        # if n == 2:
        #     return f2
        # f3 = min(f0+9, f1+4, f2+1)+costs[2]
        for i in range(2, n):
            # print(f0, f1, f2, costs[i])
            f0, f1, f2 = f1, f2, min(f0+9, f1+4, f2+1)+costs[i]
            # print(f0, f1, f2)
        return f2

        # 递推 f[i] = min(f[i-1]+1, f[i-2]+4, f[i-3]+9)+costs[i-1]   
        f = [0]*(n+1)
        for i in range(n):
            f[i+1] = min(
                f[i]+1,
                f[i-1]+4 if i > 0 else inf,
                f[i-2]+9 if i > 1 else inf,
            )+costs[i]
        # print(f)
        return f[-1]

        # 记忆化搜索
        @cache
        def dfs(i:int)->int: # 从下标i开始往下的最低总成本
            if i <= 0:
                return 0 
            return min(
                dfs(i-1) + 1,
                (dfs(i-2) + 4) if i > 1 else inf,
                (dfs(i-3) + 9) if i > 2 else inf,
            ) + costs[i-1]
        
        return dfs(n)

213. 打家劫舍 II

https://leetcode.cn/problems/house-robber-ii/description/

class Solution:
    def rob1(self, nums: List[int]) -> int:
        f0 = f1 = 0
        for x in nums:
            f0, f1 = f1, max(f1, f0 + x)
        return f1

    def rob(self, nums: List[int]) -> int:
        return max(nums[0]+self.rob1(nums[2:-1]), self.rob1(nums[1:]))

740. 删除并获得点数

https://leetcode.cn/problems/delete-and-earn/description/

class Solution:
    def deleteAndEarn(self, nums: List[int]) -> int:
        rec = [0]*10001
        for num in nums:
            rec[num] += num 
        @cache
        def dfs(i:int):
            if i < 0:
                return 0
            return max(dfs(i-2)+rec[i], dfs(i-1))
        return dfs(10000)

2466. 统计构造好字符串的方案数

https://leetcode.cn/problems/count-ways-to-build-good-strings/description/

class Solution:
    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:
        # 递推 f[i]= (f(i-zero) if i >= zero else 0) + (f(i-one) if i >= one else 0)
        ans = 0
        MOD = int(1e9+7)
        f = [0]*(high+1)
        f[0]=1
        for i in range(1, high+1):
            f[i] = (f[i-zero] if i >= zero else 0) + (f[i-one] if i >= one else 0)
            f[i] %= MOD
            if i >= low:
                ans += f[i]
                ans %= MOD
        return ans
        
        # 记忆化搜索
        ans = 0
        MOD = int(1e9+7)
        @cache 
        def dfs(i:int)->int: 
            if i == 0:
                return 1 # 刚好用完才算一个串
            nonlocal ans
            res = (dfs(i-zero) if i >= zero else 0) + (dfs(i-one) if i >= one else 0)
            # print(i, res)
            if i >= low:
                ans += res 
                ans %= MOD
            return res 
        dfs(high)
        return ans % MOD

377. 组合总和 Ⅳ

https://leetcode.cn/problems/combination-sum-iv/description/

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        # 递推 f[i] = sum((f[i-num] if i>=num else 0) for num in nums)
        nums.sort()
        f = [0]*(target+1)
        f[0] = 1
        for i in range(1, target+1):
            for num in nums:
                if num > i:
                    break 
                f[i] += f[i-num]
        return f[-1]
        # 记忆化搜索
        nums.sort()
        n = len(nums)
        @cache
        def dfs(target:int):
            if target <= 0:
                return 1 if target == 0 else 0
            res = 0
            for i in range(n):
                num = nums[i]
                if num > target:
                    break 
                res += dfs(target-num)
            return res
        return dfs(target)

2266. 统计打字方案数

https://leetcode.cn/problems/count-number-of-texts/description/

class Solution:
    def countTexts(self, pressedKeys: str) -> int:
        MOD = int(1e9+7)
        # 本质上就是算每个相同的数字段可能衍生的数值变化相乘
        # 递推
        f3, f4 = [0]*100001, [0]*100001 
        f3[0], f4[0] = 1, 1
        for i in range(1, 100001):
            f3[i] = sum([
                f3[i-1],
                f3[i-2] if i > 1 else 0,
                f3[i-3] if i > 2 else 0,
            ])%MOD
            f4[i] = sum([
                f4[i-1],
                f4[i-2] if i > 1 else 0,
                f4[i-3] if i > 2 else 0,
                f4[i-4] if i > 3 else 0,
            ])%MOD

        continous_len = 0
        cur_char = pressedKeys[0]
        ans = 1
        for c in pressedKeys:
            if c == cur_char:
                continous_len += 1
            else:
                ans = (ans*f4[continous_len] if cur_char in ["7", "9"] else ans*f3[continous_len])%MOD
                # print(ans, continous_len)
                cur_char = c 
                continous_len = 1
        ans = (ans*f4[continous_len] if cur_char in ["7", "9"] else ans*f3[continous_len])%MOD
        return ans

        # 记忆化搜索
        @cache
        def dfs(i:int, step:int): # step是这个按键可对应几个字母
            if i <= 0: # 刚好用完算一个组合
                return 1 if i == 0 else 0
            res = 0
            for j in range(1, min(i, step)+1):
                res += dfs(i-j, step)
            # print(i, step, res)
            return res

        continous_len = 0
        cur_char = pressedKeys[0]
        ans = 1
        for c in pressedKeys:
            if c == cur_char:
                continous_len += 1
            else:
                ans = (ans*dfs(continous_len, 4 if cur_char in ["7", "9"] else 3))%MOD
                # print(ans, continous_len)
                cur_char = c 
                continous_len = 1
        ans = (ans*dfs(continous_len, 4 if cur_char in ["7", "9"] else 3))%MOD
        return ans

64. 最小路径和

https://leetcode.cn/problems/minimum-path-sum/description/

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        # 空间优化，由于状态只与当前行和上一行有关，所以理论上就最多两行
        n, m = len(grid), len(grid[0])
        f0, f1 = [inf]*m, [inf]*n 
        for i in range(n-1, -1, -1):
            for j in range(m-1, -1, -1):
                if i == n-1 and j == m-1:
                    f0[j] = grid[i][j]
                else:
                    f0[j] = min(
                        f1[j] if i+1<n else inf,
                        f0[j+1] if j+1<m else inf,
                    )+grid[i][j]
            f1 = f0.copy() # 由于状态转移方向正好覆盖旧值，不用重置f0
        return f0[0]
        # 递推 f[i][j] = min(f[i+1][j], f[i][j+1])+grid[i][j]
        n, m = len(grid), len(grid[0])
        f = [[0]*m for _ in range(n)]
        for i in range(n-1, -1, -1):
            for j in range(m-1, -1, -1):
                if i == n-1 and j == m-1:
                    f[i][j] = grid[i][j]
                else:
                    f[i][j] = min(
                        f[i+1][j] if i+1<n else inf,
                        f[i][j+1] if j+1<m else inf,
                    )+grid[i][j]
        # print(f)
        return f[0][0]

        # 记忆化搜索
        # 从i，j位置出发到右下角最小路径
        n, m = len(grid), len(grid[0])
        @cache
        def dfs(i:int, j:int)->int:
            if i == n-1 and j == m-1:
                return grid[i][j]
            return min(
                dfs(i+1, j) if i<n-1 else inf,
                dfs(i, j+1) if j<m-1 else inf, 
            )+grid[i][j]

        return dfs(0, 0)