网站合同建设模板,重庆网站建设eyouc,怎样加强企业网站建设,wordpress添加源代码代码随想录算法训练营第四十五天| 70.爬楼梯#xff08;进阶#xff09;、322.零钱兑换、279.完全平方数
题目
70.爬楼梯#xff08;进阶#xff09;
57.爬楼梯#xff08;第八期模拟笔试#xff09;
https://kamacoder.com/problempage.php?pid1067
题目描述
假设…代码随想录算法训练营第四十五天| 70.爬楼梯进阶、322.零钱兑换、279.完全平方数
题目
70.爬楼梯进阶
57.爬楼梯第八期模拟笔试
https://kamacoder.com/problempage.php?pid1067
题目描述
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬至多m (1 m n)个台阶。你有多少种不同的方法可以爬到楼顶呢
注意给定 n 是一个正整数。
输入描述
输入共一行包含两个正整数分别表示n, m
输出描述
输出一个整数表示爬到楼顶的方法数。
输入示例
3 2输出示例
3if __name__ __main__:n, m input().split( )n, m int(n), int(m)dp [0] * (n 1)dp[0] 1for j in range(1, n 1):for i in range(1, m 1):if j i:dp[j] dp[j - i]print(dp[-1])题目
322.零钱兑换
给你一个整数数组 coins 表示不同面额的硬币以及一个整数 amount 表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额返回 -1 。
你可以认为每种硬币的数量是无限的。
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):dp[j] min(dp[j], dp[j - coin] 1)if dp[-1] float(inf):return -1return dp[-1]class Solution:def coinChange(self, coins: List[int], amount: int) - int:dp [float(inf)] * (amount 1)dp[0] 0# 先遍历背包再物品for j in range(1, amount 1):for i in range(len(coins)):if j coins[i]:dp[j] min(dp[j], dp[j - coins[i]] 1)if dp[-1] float(inf):return -1return dp[-1]题目
279.完全平方数
给你一个整数 n 返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数其值等于另一个整数的平方换句话说其值等于一个整数自乘的积。例如1、4、9 和 16 都是完全平方数而 3 和 11 不是。
class Solution:def numSquares(self, n: int) - int:nums [i ** 2 for i in range(1, n 1)]dp [float(inf)] * (n 1)dp[0] 0sqrt_num int(n ** 0.5)for i in range(1, n 1):for j in range(sqrt_num):if i nums[j]:dp[i] min(dp[i], dp[i - nums[j]] 1)return dp[-1]
