1. 题目
https://leetcode-cn.com/problems/perfect-squares/
给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
示例 1:
输入: n = 12
输出: 3
解释: 12 = 4 + 4 + 4.
示例 2:
输入: n = 13
输出: 2
解释: 13 = 4 + 9.
2. 我的AC
思路一：四平方和定理
Lagrange 四平方定理： 任何一个正整数都可以表示成不超过四个整数的平方之和。
- 结果只有1,2,3,4 四种可能
另外一个非常重要的推论
if and only if n is not of the form
for integers a and b.
满足四数平方和定理的数（这里要满足由四个数构成，小于四个不行），必定满足
原文：https://blog.csdn.net/wangsiyu34567/article/details/82825475
class Solution(object):
def numSquares(self, n):
"""
:type n: int
:rtype: int
"""
while n % 4 == 0:
n /= 4
if n % 8 == 7:
return 4
a = 0
while a**2 <= n:
b = int((n - a**2)**0.5)
if a**2 + b**2 == n:
return (not not a) + (not not b)
a += 1
return 3
思路二：动态规划
3. 小结
- 取整函数
- 向下取整
int()函数
>>> a = 3.75
>>> int(a) # 3
- 四舍五入
round()函数
>>> round(3.25); round(4.85)
3.0
5.0
- 向上取整
math模块中的ceil()方法
>>> a = 3.75
>>> int(a) # 3
- 判断一个数字类型
isinstance(num, int) # False, True
- 平方根
num ** 0.5
- 判断是否为正整数
not not num
(not not a) + (not not b) # a和b是否为正整数，
# 都为正整数的话返回2，只有一个是正整数的话返回1
