《算法通关之路》-chapter9动态规划-Toy模板网

这篇具有很好参考价值的文章主要介绍了《算法通关之路》-chapter9动态规划。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

《算法通关之路》学习笔记，记录一下自己的刷题过程，详细的内容请大家购买作者的书籍查阅。

爬楼梯

力扣第70题
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

'''
方法二：动态规划
时间复杂度：O（n）
空间复杂度：O（n）
'''
class Solution:
    def climbStairs(self, n: int) -> int:
        if n < 2:
            return n
        dp = [0] * (n + 1)
        dp[1], dp[2] = 1, 2
        for i in range(3, n + 1):
            dp[i] = dp[i-1] + dp[i-2]
        return dp[n]
    
n = 2
solu = Solution()
solu.climbStairs(n)

'''
方法二：动态规划（优化空间）
时间复杂度：O（n）
空间复杂度：O（1）
'''
class Solution:
    def climbStairs(self, n: int) -> int:
        if n < 2:
            return n
        fir, sec = 1, 2
        for i in range(3, n + 1):
            fir, sec = sec, fir + sec
        return sec

n = 3
solu = Solution()
solu.climbStairs(n)

打家劫舍

力扣第198题
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。

'''
方法一：递归（超时）
时间复杂度：O（2^n）
空间复杂度：O（n）
'''
class Solution:
    def rob(self, nums: list[int]) -> int:
        if len(nums) == 0:
            return 0
        return max(self.rob(nums[1:]), nums[0] + self.rob(nums[2:]))

nums = [1,2,3,1]
solu = Solution()
solu.rob(nums)

'''
方法二：递记忆化递归
时间复杂度：O（n）
空间复杂度：O（n）
'''
class Solution:
    def rob(self, nums: list[int]) -> int:
        memo = [-1] * (len(nums) + 1)
        memo[-1] = 0

        def helper(n: int, nums: list[int], memo: list[int]) -> int:
            if n >= len(nums):
                return 0
            if memo[n] != -1:
                return memo[n]
            memo[n] = max(helper(n+1, nums, memo), nums[n] + helper(n+2, nums, memo))
            return memo[n]
        
        return helper(0, nums, memo)

nums = [1,2,3,1]
solu = Solution()
solu.rob(nums)

'''
方法三：动态规划
时间复杂度：O（n）
空间复杂度：O（n）
'''
class Solution:
    def rob(self, nums: list[int]) -> int:
        n = len(nums)
        dp = [0] * (n+2)
        for i in range(0, len(nums)):
            dp[i+2] = max(dp[i] + nums[i], dp[i+1])
        return dp[n+1]

nums = [1,2,3,1]
solu = Solution()
solu.rob(nums)

'''
方法四：动态规划（优化空间）
时间复杂度：O（n）
空间复杂度：O（1）
'''
class Solution:
    def rob(self, nums: list[int]) -> int:
        curr, prev = 0, 0
        for i in range(0, len(nums)):
            prev, curr = curr, max(prev + nums[i], curr)
        return curr

nums = [1,2,3,1]
solu = Solution()
solu.rob(nums)

打家劫舍 II

力扣第213题
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，今晚能够偷窃到的最高金额。

'''
方法四：动态规划（优化空间）
时间复杂度：O（n）
空间复杂度：O（1）
'''
class Solution:
    def rob(self, nums: list[int]) -> int:
        if len(nums) == 1:
            return nums[0]
            
        def the_most_cash(nums): # 打家劫舍中的dp
            curr, prev = 0, 0
            for i in range(0, len(nums)):
                prev, curr = curr, max(prev + nums[i], curr)
            return curr
        
        return max(the_most_cash(nums[1:]), the_most_cash(nums[:-1]))

nums = [2,3,2]
solu = Solution()
solu.rob(nums)

不同路径

力扣第62题
一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？

'''
方法一：记忆化递归（超时）
时间复杂度：O（mn）
空间复杂度：O（mn）
'''
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        visited = dict()
        if m == 1 or n == 1:
            return 1
        if (m, n) in visited:
            return visited[(m, n)]
        cnt = self.uniquePaths(m, n-1) + self.uniquePaths(m-1, n)
        visited[(m, n)] = cnt
        return cnt

m, n = 3, 7
solu = Solution()
solu.uniquePaths(m, n)

'''
方法二：动态规划
时间复杂度：O（mn）
空间复杂度：O（mn）
'''
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[1] * n for _ in range(m)]
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[m-1][n-1]

m, n = 3, 7
solu = Solution()
solu.uniquePaths(m, n)

'''
方法三：动态规划（滚动数组）
时间复杂度：O（mn）
空间复杂度：O（n）
'''
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [1] * n
        for i in range(1, m):
            for j in range(1, n):
                dp[j] += dp[j-1]
        return dp[n-1]

m, n = 3, 7
solu = Solution()
solu.uniquePaths(m, n)

零钱兑换

力扣第322题
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。

'''
方法一：动态规划
时间复杂度：O（mn）
空间复杂度：O（n）
'''
class Solution:
    def coinChange(self, coins: list[int], amount: int) -> int:
        if amount == 0:
            return 0
        dp = [amount+1] * (amount+1)
        dp[0] = 0
        for i in range(1, amount+1):
            for coin in coins:
                if coin <= i:
                    dp[i] = min(dp[i], dp[i-coin]+1)
        return -1 if dp[amount] == amount + 1 else dp[amount]

coins, amount = [1, 2, 5], 11
solu = Solution()
solu.coinChange(coins, amount)

零钱兑换 II

力扣第518题
给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
假设每一种面额的硬币有无限个。
题目数据保证结果符合 32 位带符号整数。

'''
方法一：动态规划
时间复杂度：O（mn）
空间复杂度：O（n）
'''
class Solution:
    def change(self, amount: int, coins: list[int]) -> int:
        dp = [0] * (amount+1)
        dp[0] = 1
        for coin in coins:
            for i in range(coin, amount+1):
                if coin <= i:
                    dp[i] += dp[i-coin]
        return dp[amount]

amount, coins = 5, [1, 2, 5]
solu = Solution()
solu.change(amount, coins)