专业的培训行业网站制作,网页制作题库,上海医疗旅游开发网站建设,专业企业网站开发公司原问题#xff1a;给定一个非负整数n#xff0c;如果把它视作一些完全平方数的和#xff0c;那么最少需要多少个完全平方数#xff1f;
这次学习到一个热心网友的解法#xff1a;把问题转化兑换零钱问题#xff0c;然后使用动态规划求解。 比如#xff0c;给定 n12, 那…原问题给定一个非负整数n如果把它视作一些完全平方数的和那么最少需要多少个完全平方数
这次学习到一个热心网友的解法把问题转化兑换零钱问题然后使用动态规划求解。 比如给定 n12, 那么我们可以列举出可能的完全平方数{1,4,9}。此时如果把这些完全平方数视作可获得的硬币面值把n视作待兑换零钱的总数那么问题就是求“最少需要多少种硬币能够把n换成零钱如果兑换不成功那么返回-1.”
class Solution:def numSquares(self, amount: int) - int:coinsgen_coins(amount) # 找到可能的完全平方数即 硬币面值coins_kindslen(coins) # 有多少种 硬币面值dp[[inf]*(amount1) for _ in range(coins_kinds1)]# dp[i][j] 表示 使用前j种面值的硬币不一定用尽要凑出i元钱的最少需要的硬币面值种类数dp[0][0]0 for idx,val in enumerate(coins): # 第idx种硬币的面值为valfor money in range(amount1): # 待兑换的总数 moneyif moneyval: # 当前硬币的面值太大了用不上dp[idx1][money]dp[idx][money]else: # 考虑‘不用当前面值的硬币’和‘用当前面值的硬币’两种情况dp[idx1][money]min(dp[idx][money],dp[idx1][money-val]1)ansdp[coins_kinds][amount]return ans if ansinf else -1def gen_coins(amount):vals[]for i in range(1,101):if i*iamount: # 注意这里是vals.append(i*i)else:breakreturn vals
