完全平方数

力扣 279. 完全平方数

题目说明

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
提示：
- 1 <= n <= 10^4

示例

示例 1：

1
2
3

输入：n = 12
输出：3 
解释：12 = 4 + 4 + 4

示例 2：

1
2
3

输入：n = 13
输出：2
解释：13 = 4 + 9

笔者理解

此题是一道动态规划算法问题，在力扣题库中被定义为中等题。

解法

当笔者阅读完此题后，发现此题可以使用数学原理，还可以使用动态规划，让我们来看看具体如何实现的吧。

实现

class Solution {
    /*
     * 数学原理：任何一个数可以表示成不超过四个数平方的总和
     */
    public int numSquares1(int n) {
        // 判4：一个数最少可以拆成4个数的平方和，则这个数还满足 n = (4^a)*(8b+7) 
        while(n % 4 == 0) {
            n /= 4;  
        } 
        if(n % 8 == 7) {
            return 4;
        } 

        // 判1：当前数是完全平方数
        for(int i = 0; i * i <= n; ++i) {  
            if(n - i * i == 0) {
                return 1;
            }
        }

        // 判2：两个平方数的和
        for(int i = 0; i * i < n; ++i) {   
            for(int j = 0; j * j < n; ++j) {
                if(n - i * i - j * j == 0) {
                    return 2;
                }
            }
        }
        
        // 排除法：4、1、2，都不是，直接返回3
        return 3;
    }


    /*
     * 动态规划
     */
    public int numSquares2(int n) {
        int[] dp = new int [n + 1];

        for (int i = 0; i <= n; i++) {
            // 每个数最大的可能也就是全由一组成
            dp[i] = i;

            // 尝试小于当前j的所有与平方和的组合
            // 比如dp[5]变成了dp[4] + dp[1] = 2
            // 因为dp[n] = 1(n是平方数)，此时采用n来组成j最优
            // 所有我们枚举尝试j的最优解
            for (int j = 1; i - j * j >= 0; j++) {
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
            }
        }

        return dp[n];
    }
}