您现在的位置是:首页 >其他 >算法记录 | Day45 动态规划网站首页其他
算法记录 | Day45 动态规划
简介算法记录 | 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.零钱兑换
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状态图如下:
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]
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。