算法随想录第四十五天打卡|70. 爬楼梯 （进阶）,322. 零钱兑换 , 279.完全平方数

这道题目 爬楼梯之前我们做过，这次再用完全背包的思路来分析一遍 

代码随想录

def stairway(self,n,m):
    dp=[0]*(n+1)
    dp[0]=1
    for j in range(1,n+1):  #表示背包
        for num in range(m):  #表示物品
            if j>=num:
                dp[j]+=dp[j-num]
    return dp[n] 

总结

不太会用卡码网，不过跟组合的那道题是一样的，就用组合的模板来写了。

322. 零钱兑换  

class Solution(object):
    def coinChange(self, coins, amount):
        dp=[float('inf')]*(amount+1)  #表示i背包的容量所需要的最小的硬币个数
        dp[0]=0
        for 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

class Solution(object):
    def numSquares(self, n):
        dp=[float('inf')]*(n+1)
        dp[0]=0
        i=1  #i代表的是小于n的最大平方数
        while True:
            if (i+1)**2==n:
                return 1
            elif (i+1)**2>n:
                break
            else:
                i+=1
        for _ 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] = 0
 
        for 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毫秒。感觉答案的优化做的太好了，我觉得可以优化的地方都有优化，但是为啥它花的时间还更长了呢？