279 完全平方数

MX=10000 f=[0]+[inf]*MX for i in range(1,isqrt(MX)+1): for j in range(i*i,MX+1): f[j]=min(f[j],f[j-i*i]+1) class Solution: def numSquares(self, n: int) -> int: return f[n]

322 零钱兑换

class Solution: def coinChange(self, coins: list[int], amount: int) -> int: f=[0]+[inf]*amount for x in coins: for c in range(x,amount+1): f[c]=min(f[c],f[c-x]+1) return f[amount] if f[amount]<inf else -1

70 爬楼梯

class Solution: def climbStairs(self, n: int) -> int: f0=f1=1 for _ in range(2,n+1): f0,f1=f1,f1+f0 return f1