本文主要是介绍算法训练营Day45（动态规划7），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
70. 爬楼梯 （进阶） 卡码网：57. 爬楼梯
提醒
这道题目 爬楼梯之前做过，这次再用完全背包的思路来分析一遍
322. 零钱兑换 力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
提醒
如果求组合数就是外层for循环遍历物品，内层for遍历背包
如果求排列数就是外层for遍历背包，内层for循环遍历物品
本题先遍历物品 后遍历背包，还是先遍历背包 后遍历物品两种方法都可以
class Solution:def coinChange(self, coins: List[int], amount: int) -> int:dp = [float('inf')] * (amount + 1) # 创建动态规划数组，初始值为正无穷大dp[0] = 0 # 初始化背包容量为0时的最小硬币数量为0for coin in coins: # 遍历硬币列表，相当于遍历物品for i in range(coin, amount + 1): # 遍历背包容量if dp[i - coin] != float('inf'): # 如果dp[i - coin]不是初始值，则进行状态转移dp[i] = min(dp[i - coin] + 1, dp[i]) # 更新最小硬币数量if dp[amount] == float('inf'): # 如果最终背包容量的最小硬币数量仍为正无穷大，表示无解return -1return dp[amount] # 返回背包容量为amount时的最小硬币数量279.完全平方数 力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
提醒
本题 和 322. 零钱兑换 基本是一样的，大家先自己尝试做一做
class Solution:def numSquares(self, n: int) -> int:dp = [float('inf')] * (n + 1)dp[0] = 0for i in range(1, n + 1): # 遍历背包for j in range(1, int(i ** 0.5) + 1): # 遍历物品# 更新凑成数字 i 所需的最少完全平方数数量dp[i] = min(dp[i], dp[i - j * j] + 1)return dp[n]这篇关于算法训练营Day45（动态规划7）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
