代码随想录算法训练营第三十九天|70. 爬楼梯（进阶），322. 零钱兑换，279.完全平方数

🕗 发布于 2024-03-02 13:46 算法面试 python 力扣动态规划

系列文章目录

文章目录

系列文章目录
70. 爬楼梯（进阶）
322. 零钱兑换
279.完全平方数

70. 爬楼梯（进阶）

题目链接： 70. 爬楼梯（进阶）
题目内容： 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬至多m (1 <= m < n)个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。
视频讲解： 动态规划之完全背包，装满背包有几种方法？求排列数？| LeetCode：377.组合总和 Ⅳ

可以等同于完全背包问题：1阶，2阶，… m阶就是物品，楼顶就是背包。每一阶可以重复使用，例如跳了1阶，还可以继续跳1阶。问跳到楼顶有几种方法其实就是问装满背包有几种方法。

动态规划问题的五步曲：

确定dp数组（dp table）以及下标的含义：爬到有i个台阶的楼顶，有dp[i]种方法
确定递推公式：dp[i] += dp[i - j]
dp数组如何初始化：dp[0] = 1，下标非0的dp[j]初始化为0
确定遍历顺序：这是背包里求排列问题，即：1、2 步和 2、1 步都是上三个台阶，但是这两种方法不一样！所以需将target放在外循环，将nums放在内循环。每一步可以走多次，这是完全背包，内循环需要从前向后遍历。
举例推导dp数组

322. 零钱兑换

题目链接： 322. 零钱兑换
题目内容： 给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1 。你可以认为每种硬币的数量是无限的。
视频讲解： 动态规划之完全背包，装满背包最少的物品件数是多少？| LeetCode：322.零钱兑换

动态规划问题的五步曲：

确定dp数组（dp table）以及下标的含义：凑足总额为j所需钱币的最少个数为dp[j]
确定递推公式：dp[j] = min(dp[j - coins[i]] + 1, dp[j])
dp数组如何初始化：dp[0] = 0，下标非0的元素都是应该是最大值
确定遍历顺序：求钱币最小个数，那么钱币有顺序和没有顺序都可以，都不影响钱币的最小个数。
举例推导dp数组

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

279.完全平方数

题目链接： 279.完全平方数
题目内容： 给你一个整数 n ，返回和为 n 的完全平方数的最少数量。完全平方数是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
视频讲解： 动态规划之完全背包，换汤不换药！| LeetCode：279.完全平方数

动态规划问题的五步曲：

确定dp数组（dp table）以及下标的含义：和为j的完全平方数的最少数量为dp[j]
确定递推公式：dp[j] = min(dp[j - i * i] + 1, dp[j])
dp数组如何初始化：dp[0] = 0，下标非0的元素都是应该是最大值
确定遍历顺序：外层for遍历背包，内层for遍历物品，还是外层for遍历物品，内层for遍历背包，都是可以的
举例推导dp数组

class Solution:
    def numSquares(self, n: int) -> int:
        dp=[float('inf')]*(n+1)
        dp[0]=0
        for i in range(1,n+1):
            for j in range(1,int(i**0.5)+1):
                dp[i]=min(dp[i],dp[i-j*j]+1)
        return dp[n]

原文地址：https://blog.csdn.net/weixin_47748259/article/details/136389259

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：STM32自学☞DMA数据转运以及DMA+AD多通道案例
下一篇：划分开始结束位置&设置标记

leetcode289:生命游戏
根据，简称为，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。给定一个包含m × n个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态：1即为（live），或0即为
阅读更多2024-10-20
MongoDB数据恢复
注意：两个MongoDB的版本要一致，本文使用的是mongo:4.2.24。先把K8S上面的MongoDB 容器停止（可以把副本改成0）。1、将容器挂载MongoDB的数据目录备份到本地。经常是数据文
阅读更多2024-10-20
C#中实现事务
C#中实现事务
阅读更多2024-10-20
【LeetCode每日一题】——560.和为 K 的子数组
给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的子数组的个数。子数组是数组中元素的连续非空序列。
阅读更多2024-10-20
「漏洞复现」满客宝智慧食堂系统 selectUserByOrgId 未授权访问漏洞
请勿利用文章内的相关技术从事非法测试，由于传播、利用此文所提供的信息而造成的任何直接或者间接的后果及损失，均由使用者本人负责，作者不为此承担任何责任。工具来自网络，安全性自测，如有侵权请联系删除。本次
阅读更多2024-10-20
React面试题目（从基本到高级）
React前端面试常见题目涵盖了React的基础概念、组件、状态管理、生命周期、性能优化等多个方面。
阅读更多2024-10-20
12.个人博客系统（Java项目基于spring和vue）
1 在校学习的学生，可用于日常学习使用或是毕业设计使用 2 毕业一到两年的开发人员，用于锻炼自己的独立功能模块设计能力，增强代码编写能力。 3 亦可以部署为商化项目使用。 4 需要完整资料及源码
阅读更多2024-10-20
YoloV8改进策略：注意力改进|DeBiFormer，可变形双级路由注意力|引入DeBiLevelRoutingAttention注意力模块（全网首发）
本次改进的核心在于将DeBiLevelRoutingAttention模块嵌入到YoloV8的主干网络中，具体位置是在SPPF（Spatial Pyramid Pooling Fast）模块之后。这一
阅读更多2024-10-20
word取消自动单词首字母大写
情况说明：在word输入单词后首字母会自动变成大写取消单词首字母大写步骤：（1）点击菜单栏文件（2）点击“更多”——>“选项”（3）点击“校对”——>“自动更正选项”（4）取消“句首字母大
阅读更多2024-10-20
web前端网页用户注册页面
【代码】web前端网页用户注册页面。
阅读更多2024-10-20

代码随想录算法训练营第三十九天|70. 爬楼梯 （进阶），322. 零钱兑换，279.完全平方数

系列文章目录

文章目录

70. 爬楼梯 （进阶）

322. 零钱兑换

279.完全平方数

相关文章

代码随想录算法训练营第三十九天|70. 爬楼梯（进阶），322. 零钱兑换，279.完全平方数

70. 爬楼梯（进阶）