一、题目

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

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

二、题解

2.1 数学解

规律：

1. 四平方和定理：每个正整数都可以表示为至多4个正整数的平方和。
2. 任何消掉4的因子，结论不变
3. 模8等于7的数，一定是有四个数的平方和组成

   public int numSquares(int n) {
    
        while (n%4==0){
    
            n=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&&b>0)?2:1;
            }
        }
        return 3;
    }

2.2 动态规划

  public int numSquares(int n) {
    
        int[] dp = new int[n + 1]; // 默认初始化值都为0
        for (int i = 1; i <= n; i++) {
    
            dp[i] = i; // 最坏的情况就是每次+1
            for (int j = 1; i - j * j >= 0; j++) {
    
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1); // 动态转移方程
            }
        }
        return dp[n];
    }