322 零钱对兑换
给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1 。
你可以认为每种硬币的数量是无限的。
# 先物品后背包
def coinChange(coins:'list[int]',amount:int)->int:
dp=[float{'inf'}]*(amount+1)
dp[0]=0
for coin in coins:
for i in range(coin,amount+1):
if dp[i-coin]!=float('inf):
dp[i]=min(dp[i-coin]+1,dp[i])
if dp[amount]==float('inf'):
return -1
return dp[amount]
# 先背包后物品
def coinChange(coins,amount):
dp=[float{'inf'}]*(amount+1)
dp[0]=0
for i in range(1,amount+1):
for j in range(len(coins)):
if i-coins[j]>=0 and dp[i-coins[j]]!=float('inf')
dp[i]=min(dp[i-coins[j]]+1,dp[i])
if dp[amount]==float('inf'):
return -1
return dp[amount]
279 完全平方数
给你一个整数 n ,返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,1、4、9 和 16 都是完全平方数,而 3 和 11 不是
def numSquares(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):#物品
dp[i]=min(dp[i],dp[i-j*j]+1)
return dp[n]
def numSquares(n):
dp=[float('inf')]*(n+1)
dp[0]=0
for i in range(1,int(n**0.5)+1):#物品
for j in range(i*i,n+1):#背包
dp[j]=min(dp[j-i*i],dp[j])
return dp[n]
def numSquares(n):
dp=[float('inf')]*(n+1)
dp[0]=0
for i in range(1,n+1):
j=1
while j*j<=i:
dp[i]=min(dp[i],dp[i-j*j]+1)
j+=1
return dp[n]