您现在的位置是:首页 >其他 >算法记录 | Day45 动态规划网站首页其他

算法记录 | Day45 动态规划

是菜鸡小小陈啊 2023-06-26 04:00:02
简介算法记录 | Day45 动态规划

70.爬楼梯 (进阶)

改为:一步一个台阶,两个台阶,三个台阶,…,直到 m个台阶。问有多少种不同的方法可以爬到楼顶呢?

1阶,2阶,… m阶就是物品,楼顶就是背包。

每一阶可以重复使用,例如跳了1阶,还可以继续跳1阶。

问跳到楼顶有几种方法其实就是问装满背包有几种方法。

此时大家应该发现这就是一个完全背包问题了!

1.确定dp数组以及下标的含义:dp[i]:爬到有i个台阶的楼顶,有dp[i]种方法。

2.确定递推公式:dp[i] += dp[i - j]
dp[i]有几种来源,dp[i - 1],dp[i - 2],dp[i - 3] 等等,即:dp[i - j]

3.dp数组如何初始化:dp[0]=1

4.确定遍历顺序:这是背包里求排列问题,即:1、2 步 和 2、1 步都是上三个台阶,但是这两种方法不一样!

所以需将target放在外循环,将nums放在内循环。每一步可以走多次,这是完全背包,内循环需要从前向后遍历。

class Solution:
    def climbStairs(self, n: int) -> int:
        dp = [0]*(n + 1)
        dp[0] = 1
        m = 2
        # 遍历背包
        for j in range(n + 1):
            # 遍历物品
            for step in range(1, m + 1):
                if j >= step:
                    dp[j] += dp[j - step]
        return dp[n]

322.零钱兑换

322.零钱兑换

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [float("inf")]*(amount+1)
        dp[0] = 0
        for i in range(len(coins)):
            for j in range(coins[i],amount+1):
                dp[j] = min(dp[j],dp[j-coins[i]]+1)
        return dp[amount] if dp[amount] != float("inf") else -1

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [float("inf")]*(amount+1)
        dp[0] = 0
        for i in range(1,amount+1):
            for coin in coins:
                if i >= coin:
                    dp[i] = min(dp[i],dp[i-coin]+1)
        return dp[amount] if dp[amount] != float("inf") else -1

279.完全平方数

思路:

1.确定dp数组以及下标的含义:dp[j]:和为j的完全平方数的最少数量为dp[j]

2.确定递推公式:dp[j] = min(dp[j - i * i] + 1, dp[j])

dp[j] 可以由dp[j - i * i]推出, dp[j - i * i] + 1 便可以凑成dp[j]。

3.dp数组如何初始化:dp[0]表示和为0的完全平方数的最小数量,那么dp[0]一定是0。非0下标的dp[j]一定要初始为最大值,这样dp[j]在递推的时候才不会被初始值覆盖

4.遍历顺序 :本题外层for遍历背包,内层for遍历物品,还是外层for遍历物品,内层for遍历背包,都是可以的

5.举例来推导dp数组:

已输入n为5例,dp状态图如下:

279.完全平方数

class Solution:
    def numSquares(self, n: int) -> int:
        '''版本一,先遍历背包, 再遍历物品'''
        # 初始化
        nums = [i**2 for i in range(1, n + 1) if i**2 <= n]
        dp = [10**4]*(n + 1)
        dp[0] = 0
        # 遍历背包
        for j in range(1, n + 1):
            # 遍历物品
            for num in nums:
                if j >= num:
                    dp[j] = min(dp[j], dp[j - num] + 1)
        return dp[n]
    
    def numSquares1(self, n: int) -> int:
        '''版本二, 先遍历物品, 再遍历背包'''
        # 初始化
        nums = [i**2 for i in range(1, n + 1) if i**2 <= n]
        dp = [10**4]*(n + 1)
        dp[0] = 0
        # 遍历物品
        for num in nums:
            # 遍历背包
            for j in range(num, n + 1):
                dp[j] = min(dp[j], dp[j - num] + 1)
        return dp[n]
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。