今日任务：
1）卡码网57. 爬楼梯（70. 爬楼梯进阶版）
2）322.零钱兑换
3）279.完全平方数
4）复习day14
卡码网57. 爬楼梯（70. 爬楼梯进阶版）
题目链接：57. 爬楼梯（第八期模拟笔试） (kamacoder.com)
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬至多m (1 <= m < n)个台阶。你有多少种不同的方法可以爬到楼顶呢？ 注意：给定 n 是一个正整数。 输入描述：输入共一行，包含两个正整数，分别表示n, m 输出描述：输出一个整数，表示爬到楼顶的方法数。 输入示例：3 2 输出示例：3 提示： 当 m = 2，n = 3 时，n = 3 这表示一共有三个台阶，m = 2 代表你每次可以爬一个台阶或者两个台阶。 此时你有三种方法可以爬到楼顶。 1 阶 + 1 阶 + 1 阶段 1 阶 + 2 阶 2 阶 + 1 阶
文章讲解：代码随想录 (programmercarl.com)
思路：
这是之前70爬楼梯的变体，之前70是只能至多爬两个台阶
这次改为：一步一个台阶，两个台阶，三个台阶，.......，直到 m个台阶。问有多少种不同的方法可以爬到楼顶呢？
这其实是一个求排列组合的完全背包问题。
1阶，2阶，.... m阶就是物品，楼顶就是背包。
每一阶可以重复使用，例如跳了1阶，还可以继续跳1阶。
问跳到楼顶有几种方法其实就是问装满背包有几种方法。
- 我们定义一个一维数组
dp，其中dp[i]表示爬到第i阶楼梯的方法数。初始状态dp[0] = 1，因为爬到第 0 阶楼梯有一种方法，即不爬。- 然后我们从第 1 阶开始遍历到第
n阶，对于每一阶楼梯，我们考虑可以从前面的m个楼梯中的任意一个跳过来，因此dp[i] = dp[i-1] + dp[i-2] + ... + dp[i-m]。
def climbing_stairs(n,m):
# 背包总容量
dp = [0]*(n+1)
dp[0] = 1
# 排列题，注意循环顺序，背包在外物品在内5
for j in range(n+1):
for i in range(1,m+1):
if j >= i:
dp[j] += dp[j - i] # 这里i就是物品重量而非index
return dp[-1]
if __name__ == '__main__':
n,m = list(map(int,input().split(' ')))
print(climbing_stairs(n,m))322.零钱兑换
题目链接：322. 零钱兑换 - 力扣（LeetCode）
给定不同面额的硬币 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 示例 4： 输入：coins = [1], amount = 1 输出：1 示例 5： 输入：coins = [1], amount = 2 输出：2 提示： 1 <= coins.length <= 12 1 <= coins[i] <= 2^31 - 1 0 <= amount <= 10^4
文章讲解：代码随想录 (programmercarl.com)
视频讲解：动态规划之完全背包，装满背包最少的物品件数是多少？| LeetCode：322.零钱兑换哔哩哔哩bilibili
思路：
题目中说每种硬币的数量是无限的，可以看出是典型的完全背包问题。
但是是求最小数硬币数，也就是说不涉及排列，所以这题我们应该先遍历物品，也就是硬币，再遍历背包容量。
硬币可以重复，那我们应该从前往后遍历
1.确定dp数组以及下标的含义
dp[j]：凑足总额为j所需钱币的最少个数为dp[j]
2.确定递推公式
凑足总额为j - coins[i]的最少个数为dp[j - coins[i]]，那么只需要加上一个钱币coins[i]即dp[j - coins[i]] + 1就是dp[j]（考虑coins[i]）
所以dp[j] 要取所有 dp[j - coins[i]] + 1 中最小的。
递推公式：dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
3.dp数组如何初始化
首先凑足总金额为0所需钱币的个数一定是0，那么dp[0] = 0;
其他下标对应的数值呢？
考虑到递推公式的特性，dp[j]必须初始化为一个最大的数，否则就会在min(dp[j - coins[i]] + 1, dp[j])比较的过程中被初始值覆盖。
所以下标非0的元素都是应该是最大值。
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
# 初始化动态规划数组，初始值为正无穷，表示无法凑成任何金额
dp = [float('inf')]*(amount+1)
# 设置总金额为0时需要的硬币个数为0
dp[0] = 0
# 遍历硬币面额
for coin in coins:
# 从当前硬币面额开始，遍历到总金额，更新动态规划数组
for j in range(coin,amount+1):
# 动态规划转移方程，更新当前总金额所需的最少硬币个数
dp[j] = min(dp[j],dp[j-coin]+1)
# 如果最终总金额对应的动态规划数组值仍然是正无穷，则表示无法凑成总金额，返回-1
# 否则返回最终总金额对应的动态规划数组值
return -1 if dp[-1] == float('inf') else dp[-1]
if __name__ == '__main__':
obj = Solution()
# coins,amount = [1, 2, 5],11
# coins,amount = [2],3
coins,amount = [1],0
print(obj.coinChange(coins, amount))279.完全平方数
题目链接：279. 完全平方数 - 力扣（LeetCode）
给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。 给你一个整数 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
文章讲解：代码随想录 (programmercarl.com)
视频讲解：动态规划之完全背包，换汤不换药！| LeetCode：279.完全平方数哔哩哔哩bilibili
思路：
- 创建一个动态规划数组dp，其中dp[j]表示和为j的完全平方数的最少数量。
- 初始化dp数组，将dp[0]设置为0，其他元素设置为正无穷。
- 遍历从1到n的所有数num，对于每个数num，遍历从num*num到n的所有可能的和j。
- 对于每个可能的和j，更新dp[j]，将其设置为dp[j]和dp[j-num*num]+1的较小值，表示如果选择当前的完全平方数num，所需的硬币数量。
- 最终返回dp[n]作为结果，表示和为n的完全平方数的最少数量。
class Solution:
def numSquares(self, n: int) -> int:
# 创建动态规划数组，dp[j]表示和为j的完全平方数的最少数量
dp = [float('inf')]*(n+1)
dp[0] = 0# 初始化和为0时的数量为0
# 计算不超过n的最大完全平方数
max_num = int(n ** 0.5) + 1
# 遍历从1到n的所有可能的完全平方数
for num in range(1,max_num + 1):
# 遍历从num*num到n的所有可能的和
for j in range(num*num,n+1):
if j >= num*num:
# 更新dp[j]，选择较小的值表示当前和的最少数量
dp[j] = min(dp[j],1+dp[j-num*num])
return dp[-1]
