【leetcode279】完全平方数,动态规划解法

原问题：给定一个非负整数n，如果把它视作一些完全平方数的和，那么最少需要多少个完全平方数？

这次学习到一个热心网友的解法：把问题转化兑换零钱问题，然后使用动态规划求解。
比如，给定 n=12, 那么我们可以列举出可能的完全平方数{1,4,9}。此时，如果把这些完全平方数视作可获得的硬币面值，把n视作待兑换零钱的总数，那么问题就是求“最少需要多少种硬币，能够把n换成零钱？如果兑换不成功，那么返回-1.”）

class Solution:def numSquares(self, amount: int) -> int:coins=gen_coins(amount) # 找到可能的完全平方数，即 硬币面值coins_kinds=len(coins) # 有多少种 硬币面值dp=[[inf]*(amount+1) for _ in range(coins_kinds+1)]# dp[i][j] 表示 使用前j种面值的硬币（不一定用尽）要凑出i元钱的最少需要的硬币面值种类数dp[0][0]=0 for idx,val in enumerate(coins): # 第idx种硬币的面值为valfor money in range(amount+1): # 待兑换的总数 moneyif money<val: # 当前硬币的面值太大了，用不上，dp[idx+1][money]=dp[idx][money]else: # 考虑‘不用当前面值的硬币’和‘用当前面值的硬币’两种情况dp[idx+1][money]=min(dp[idx][money],dp[idx+1][money-val]+1)ans=dp[coins_kinds][amount]return ans if ans<inf else -1def gen_coins(amount):vals=[]for i in range(1,101):if i*i<=amount: # ！！ 注意这里是<=vals.append(i*i)else:breakreturn vals