LeetCode 279. Perfect Squares（完美平方）

原题网址：https://leetcode.com/problems/perfect-squares/

Given a positive integer n, find the least number of perfect square numbers (for example, 

1, 4, 9, 16, ...

) which sum to n.

For example, given n = 

12

, return 

3

 because 

12 = 4 + 4 + 4

; given n = 

13

, return 

2

 because 

13 = 4 + 9

.

方法一：动态规划。这是一道非常非常典型的动态规划问题。

1. 首先如何定义问题？这个问题就是，f(i)=对于任意一个正整数i，求i由多少个整数平方和组成。

2. 如何得到最终问题f(n)？方法就是从1开始计算，f(1)，f(2)，直到f(n)

3. 每个f(i)如何计算？每个f(i)只和前面的f值有关！！！

public class Solution {
    public int numSquares(int n) {
        int[] nums = new int[n+1];
        for(int i=1; i<=n; i++) nums[i] = i;
        for(int i=2; i<=n; i++) {
            for(int j=1; j*j<=i; j++) {
                nums[i] = Math.min(nums[i], nums[i-j*j]+1);
            }
        }
        return nums[n];
    }
}
           

方法二：非常变态，用到“四平方和定理”

public class Solution {
    public int numSquares(int n) {
        while(n % 4 == 0) n /= 4;
        if (n % 8 == 7) return 4;
        
        for(int a = 0; a * a <= n; ++a) {
            int b = (int)Math.sqrt(n - a * a);
            if (a * a + b * b == n) return (a==0?0:1) + (b==0?0:1);
        }
        
        return 3;
    }
}
           

我没有做出来，参考：

http://storypku.com/2015/10/leetcode-question-279-perfect-squares/

https://zh.wikipedia.org/wiki/%E5%9B%9B%E5%B9%B3%E6%96%B9%E5%92%8C%E5%AE%9A%E7%90%86