算法随想录第四十五天打卡|70. 爬楼梯 （进阶）,322. 零钱兑换 , 279.完全平方数
70. 爬楼梯 （进阶）
这道题目 爬楼梯之前我们做过，这次再用完全背包的思路来分析一遍
代码随想录
def stairway(self,n,m):dp=[0]*(n+1)dp[0]=1for j in range(1,n+1): #表示背包for num in range(m): #表示物品if j>=num:dp[j]+=dp[j-num]return dp[n] 总结
不太会用卡码网，不过跟组合的那道题是一样的，就用组合的模板来写了。
322. 零钱兑换
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环
遍历物品。
这句话结合本题 大家要好好理解。
视频讲解：动态规划之完全背包，装满背包最少的物品件数是多少？| LeetCode：322.零钱兑换_哔哩哔哩_bilibili
代码随想录
思路
这道题要改的是dp的定义和方程式。
class Solution(object):def coinChange(self, coins, amount):dp=[float('inf')]*(amount+1) #表示i背包的容量所需要的最小的硬币个数dp[0]=0for coin in coins:for j in range(coin,amount+1):dp[j]=min(dp[j],dp[j-coin]+1)return dp[amount] if dp[amount]!=float('inf') else -1总结
开始还用的0作为初始量，结果都是零。
279.完全平方数
本题 和 322. 零钱兑换 基本是一样的，大家先自己尝试做一做
视频讲解：动态规划之完全背包，换汤不换药！| LeetCode：279.完全平方数_哔哩哔哩_bilibili
代码随想录
class Solution(object):def numSquares(self, n):dp=[float('inf')]*(n+1)dp[0]=0i=1 #i代表的是小于n的最大平方数while True:if (i+1)**2==n:return 1elif (i+1)**2>n:breakelse:i+=1for _ in range(1,i+1): num=_**2 #代表的是物品for j in range(num,n+1):dp[j]=min(dp[j],dp[j-num]+1)return dp[n]class Solution:def numSquares(self, n: int) -> int:dp = [float('inf')] * (n + 1)dp[0] = 0for i in range(1, n + 1): # 遍历背包for j in range(1, int(i ** 0.5) + 1): # 遍历物品# 更新凑成数字 i 所需的最少完全平方数数量dp[i] = min(dp[i], dp[i - j * j] + 1)return dp[n]总结
确实是基本一样，但是感觉优化空间很大，我用了2000毫秒，但最快的是40毫秒。感觉答案的优化做的太好了，我觉得可以优化的地方都有优化，但是为啥它花的时间还更长了呢？