宠物网站 html模板,小店网站怎么做,重庆秀山网站建设,中国物联网公司排名一、爬楼梯#xff08;进阶版#xff09; 1.1 题目
题目描述
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬至多m (1 m n)个台阶。你有多少种不同的方法可以爬到楼顶呢#xff1f;
注意#xff1a;给定 n 是一个正整数。
输入描述
输入共一…一、爬楼梯进阶版 1.1 题目
题目描述
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬至多m (1 m n)个台阶。你有多少种不同的方法可以爬到楼顶呢
注意给定 n 是一个正整数。
输入描述
输入共一行包含两个正整数分别表示n, m
输出描述
输出一个整数表示爬到楼顶的方法数。
输入示例
3 2
输出示例
3 1.2 题目链接 57.爬楼梯 1.3 解题思路与过程想法 1解题思路 # 分析这道题是 70.爬楼梯 的进阶版对于每次爬楼的最多阶数是个不定值 n。是个典型的背包的排列问题。 排列问题121 和 211 是两种不同方法 数组爬到 i 阶有 dp[i] 种方法 递推关系求组成的方法数——————dp[j] dp[j-i] 求背包装载的最大“价值” ——dp[j] max(dp[j], dp[j-weight[i]]value[i]) 求背包装载的最少“数量” ——dp[j] min(dp[j], dp[j-weight[i]]1) 初始化求组成的方法数——dp[0] 1 其他值初始化———初始化不影响覆盖的值求最大--初始化最小 求最小--初始化无穷大值 遍历顺序因为是排列问题所以先遍历背包容量后遍历物体 此处 weight[i] 对应着 本次爬楼的阶数 value[i] 对应着 一次爬楼 2过程想法 比较经典思路也比较好想但需注意是排列问题 1.4 代码
def up(n,m) - int:# 物品是每次爬的楼梯数可重复----完全背包# 背包容量 n物品 1~m# 数组爬到 i 阶有 dp[i] 种方法dp [0] * (n1)# 递推关系dp[j] dp[j-i]# 初始化求方法数一般初始化 dp[0] 1若是0则后续将全是 0 dp[0] 1for j in range(1,n1): # 遍历背包for i in range(1,m1): # 遍历物体if j i:dp[j] dp[j-i]return dp[n]if __name__ __main__:# 从键盘端一次性连续读取两个数字inputs input()# 将输入拆分为两个数字num1, num2 map(int, inputs.split())print(up(num1,num2))
二、零钱兑换 2.1 题目 给你一个整数数组 coins 表示不同面额的硬币以及一个整数 amount 表示总金额。 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额返回 -1 。 你可以认为每种硬币的数量是无限的。
示例 1
输入coins [1, 2, 5], amount 11输出3解释11 5 5 1
示例 2
输入coins [2], amount 3输出-1
示例 3
输入coins [1], amount 0
输出0提示
1 coins.length 121 coins[i] 2^31 - 10 amount 10^4 2.2 题目链接 322.零钱兑换 2.3 解题思路与过程想法 1解题思路 # 数组构成总金额 j 所需的最少硬币数 dp[j] # 初始化初始一个不会覆盖其他值的原始值求最小赋无穷大 # 递推关系dp[j] min(dp[j],dp[j-coin]1) # 完全背包的组合问题先遍历物体后遍历背包容量 2过程想法 针对纯完全背包问题变化不是很大代码比较好写 2.4 代码
class Solution:def coinChange(self, coins: List[int], amount: int) - int:# 完全背包组合问题# 数组构成总金额 j 所需的最少硬币数 dp[j]# 初始化初始一个不会覆盖其他值的原始值dp [float(inf)] * (amount1)# 递推关系dp[j] min(dp[j],dp[j-coin]1)# 初始化 dp[0] 0# 举例递推 for coin in coins: # 遍历物品for j in range(coin,amount1): # 遍历背包dp[j] min(dp[j],dp[j-coin]1)return dp[amount] if dp[amount] ! float(inf) else -1
三、完全平方数 3.1 题目 给你一个整数 n 返回 和为 n 的完全平方数的最少数量 。 完全平方数 是一个整数其值等于另一个整数的平方换句话说其值等于一个整数自乘的积。例如1、4、9 和 16 都是完全平方数而 3 和 11 不是。
示例 1
输入n 12
输出3
解释12 4 4 4
示例 2
输入n 13
输出2
解释13 4 9提示
1 n 10^4 3.2 题目链接 279.完全平方数 3.3 解题思路与过程想法 1解题思路 分析整个题目的变体主要在于“完全平方数”为了便于遍历以其需“平方”的数为遍历数。 # 数组i 最少可由 dp[i] 个完全平方数组成 # 初始化初始一个不会覆盖其他值的原始值求最小赋无穷大 # 递推关系dp[j] min(dp[j],dp[j-i*i]1) # 完全背包的组合问题先遍历物体后遍历背包容量 2过程想法 分析出变化的关系代码是很好写的 3.4 代码
class Solution:def numSquares(self, n: int) - int:# 完全背包问题-组合问题# 数组i 最少可由 dp[i] 个完全平方数组成dp [float(inf)] * (n1)# 递推关系dp[j] min(dp[j],dp[j-i*i]1)# 初始化dp[0] 0for i in range(n//21): # 遍历物体for j in range(i*i,n1): # 遍历背包dp[j] min(dp[j], dp[j - i*i]1)# 处理边界情况return dp[n] if n ! 1 else 1
