阿里巴巴国际站做2个网站有用吗,wordpress js放到oss,wordpress 可视化表格,网站关键词提交题干#xff1a;
给定正整数 n#xff0c;找到若干个完全平方数#xff08;比如 1, 4, 9, 16, ...#xff09;使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
示例 1:
输入: n 12
输出: 3
解释: 12 4 4 4.
示例 2:
输入: n 13
输出: 2
解释: 13 …题干
给定正整数 n找到若干个完全平方数比如 1, 4, 9, 16, ...使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
示例 1:
输入: n 12
输出: 3
解释: 12 4 4 4.
示例 2:
输入: n 13
输出: 2
解释: 13 4 9.
解题报告
很多人第一眼看到这个问题想到的第一种做法就是使用贪心算法但是对于这个问题是不适用的例如
如果贪心来做12 9 1 1 1所以答案为4了但是实际答案是3。
我们根据题目中完全平方数的个数最少看到最少想到最短路建图跑最短路就行了。一种不错的思考方式但是此题会TLE。 下面介绍一个数学定理
四平方和定理
Lagrange 四平方定理 任何一个正整数都可以表示成不超过四个整数的平方之和。万能的拉格朗日Orz
即结果只有1,2,3,4四种可能。
还有一个重要的推论 也就是说我们可以先判断这个数是否满足如果是那就ans4
处理方法是 while (myN 3 0) {myN 2;}if (myN % 8 7) {return 4;}
然后我们再暴力破解ans1和ans2的情况如果都不满足那就直接ans3。
class Solution:_dp list()def numSquares(self, n)::type n: int:rtype: intdp self._dpdp [float(inf) for i in range(n 1)]dp[0] 0for i in range(n 1):j 1while i j**2 n:dp[i j**2] min(dp[i j**2], dp[i] 1)j 1return dp[n]参考博客https://blog.csdn.net/qq_17550379/article/details/80875782
