70. 爬楼梯（进阶版）
文档讲解：代码随想录
题目链接：57. 爬楼梯（第八期模拟笔试）
我们之前做的 爬楼梯 是只能至多爬两个台阶。
这次改为：一步一个台阶，两个台阶，三个台阶，.......，直到 m个台阶。问有多少种不同的方法可以爬到楼顶呢？
这又有难度了，这其实是一个完全背包问题。
1阶，2阶，.... m阶就是物品，楼顶就是背包。
每一阶可以重复使用，例如跳了1阶，还可以继续跳1阶。
问跳到楼顶有几种方法其实就是问装满背包有几种方法。
此时大家应该发现这就是一个完全背包问题了！
和昨天的题目动态规划：377. 组合总和 Ⅳ (opens new window)基本就是一道题了。
动规五部曲分析如下：
确定dp数组以及下标的含义
dp[i]：爬到有i个台阶的楼顶，有dp[i]种方法。
确定递推公式
在动态规划：494.目标和 (opens new window)、 动态规划：518.零钱兑换II (opens new window)、动态规划：377. 组合总和 Ⅳ (opens new window)中我们都讲过了，求装满背包有几种方法，递推公式一般都是dp[i] += dp[i - nums[j]];
本题呢，dp[i]有几种来源，dp[i - 1]，dp[i - 2]，dp[i - 3] 等等，即：dp[i - j]
那么递推公式为：dp[i] += dp[i - j]
dp数组如何初始化
既然递归公式是 dp[i] += dp[i - j]，那么dp[0] 一定为1，dp[0]是递归中一切数值的基础所在，如果dp[0]是0的话，其他数值都是0了。
下标非0的dp[i]初始化为0，因为dp[i]是靠dp[i-j]累计上来的，dp[i]本身为0这样才不会影响结果
确定遍历顺序
这是背包里求排列问题，即：1、2 步 和 2、1 步都是上三个台阶，但是这两种方法不一样！
所以需将target放在外循环，将nums放在内循环。
每一步可以走多次，这是完全背包，内循环需要从前向后遍历。
n, m = map(int, input().split())
#排列问题，背包容量为n，物品重量1-m
def climbStairs(n,m):
dp = [0]*(n+1)
dp[0] = 1
#先遍历背包
for i in range(1,n+1):
for j in range(1,m+1):
if i >= j:
dp[i] += dp[i-j]
return dp[n]
print(climbStairs(n,m)) 之前的疑问解答：数组负索引为什么不会报错：负的相对于倒序来的，只要绝对值不超多数组的大小就不会报错
322. 零钱兑换
文档讲解：代码随想录
题目链接：. - 力扣（LeetCode）
第一感觉，这个题与之前的一个题有点像，不是纯完全背包，是求达到目标值的最少硬币数
dp数组含义
就看本题求什么，装满背包容量最少的物品
dp[j]:凑足总额为j所需钱币的最少个数为dp[j]
递推公式
在遍历硬币的过程中：dp[j] = min(dp[j-coins[i]]+1,dp[j])
初始化
首先凑足总金额为0所需钱币的个数一定是0，那么dp[0] = 0;
其他下标对应的数值呢？
考虑到递推公式的特性，dp[j]必须初始化为一个最大的数，否则就会在min(dp[j - coins[i]] + 1, dp[j])比较的过程中被初始值覆盖。
所以下标非0的元素都是应该是最大值。
遍历顺序
遍历顺序是很重要的,比递推公式还要难一些
本题求钱币最小个数，那么钱币有顺序和没有顺序都可以，都不影响钱币的最小个数。
所以本题并不强调集合是组合还是排列。
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
在动态规划专题我们讲过了求组合数是动态规划：518.零钱兑换II (opens new window)，求排列数是动态规划：377. 组合总和 Ⅳ (opens new window)。
所以本题的两个for循环的关系是：外层for循环遍历物品，内层for遍历背包或者外层for遍历背包，内层for循环遍历物品都是可以的！
那么我采用coins放在外循环，target在内循环的方式。
本题钱币数量可以无限使用，那么是完全背包。所以遍历的内循环是正序
（一维01背包的两层for循环的位置不可以换，且内层循环为倒序）
综上所述，遍历顺序为：coins（物品）放在外循环，target（背包）在内循环。且内循环正序。
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[amount]!= float('inf'):
return dp[amount]
return -1与代码随想录中提供的参考代码不同,如下，代码随想录在循环中还判断了dp[i - coin]是否等于float('inf')，但是上面的也是可以测试通过的。至于为什么，有待解决
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
dp = [float('inf')] * (amount + 1) # 创建动态规划数组，初始值为正无穷大
dp[0] = 0 # 初始化背包容量为0时的最小硬币数量为0
for 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 -1
return dp[amount] # 返回背包容量为amount时的最小硬币数量279.完全平方数
文档讲解：代码随想录
题目链接：. - 力扣（LeetCode）
任意正整数 n都可以找到凑成它的完全平方数，因为完全平方数中有1
目标值：正整数n
完全平方数：1，4，9，16....
将题目换一下，就是一个完全背包问题：
背包容量：正整数n
物品：1，4，9，16....
与上一题的思路也是一样的，主要就是物品没有明确说
dp数组含义
就看本题求什么，凑成正整数n最少的完全平方数
dp[j]:凑足正整数j所需完全平方数的最少个数为dp[j]
递推公式
在遍历物品的过程中：dp[j] = min(dp[j-i*i]+1,dp[j])
初始化
与上题一样
初始化为一个较大的数
遍历顺序
与上题一样，下面是一个例子
for (int i = 0; i <= n; i++) { // 遍历背包
for (int j = 1; j * j <= i; j++) { // 遍历物品
dp[i] = min(dp[i - j * j] + 1, dp[i]);
}
}主要是物品怎么表示：i*i
class Solution:
def numSquares(self, n: int) -> int:
dp = [float('inf')] *(n+1)
dp[0] = 0
#先遍历物品，再遍历背包
for i in range(1,int(n**0.5)+1):#这里并不是物品，i*i才是一个物品，这里是物品的范围
for j in range(i*i,n+1):
dp[j] = min(dp[j],dp[j-i*i]+1)
return dp[n]总结
求组合数：动态规划：518.零钱兑换II (opens new window)
求排列数：动态规划：377. 组合总和 Ⅳ (opens new window)、动态规划：70. 爬楼梯进阶版（完全背包） (opens new window)
求最小数：动态规划：322. 零钱兑换 (opens new window)、动态规划：279.完全平方数
标签：背包,进阶,int,随想录,amount,遍历,物品,第四十八,dp From： https://blog.csdn.net/qq_52149213/article/details/139397842