279. 完全平方数

解法一：动态规划

找出小于等于n的所有完全平方数，然后就是一个背包问题。

class Solution {
    public int numSquares(int n) {
        final int LEN = (int) Math.sqrt(n);
        int[] squareNumber = new int[LEN + 1];
        // squareNumber[i] = i*i
        for (int i = 1; i <= LEN; ++i) {
            squareNumber[i] = i * i;
        }
        // dp[i]表示i可以被分解成的最小完全平方和个数
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= Math.sqrt(i); ++j) {
                dp[i] = Math.min(dp[i], dp[i - squareNumber[j]] + 1);
            }
        }
        return dp[n];
    }
}

解法二：贪心+递归

参考：https://leetcode-cn.com/problems/perfect-squares/solution/wan-quan-ping-fang-shu-by-leetcode/

class Solution {
    Set<Integer> squareNumber;
    public int numSquares(int n) {
        init(n);
        for (int i = 1; i <= n; ++i) {
            if (isDividedBy(n, i)) {
                return i;
            }
        }
        return -1;
    }
    private void init(int n) {
        squareNumber = new HashSet<>();
        for (int i = 1; i * i <= n; ++i) {
            squareNumber.add(i * i);
        }
    }
    /**
     * n能否被分解为count个完全平方数
     *
     * @param n
     * @param count
     * @return
     */
    private boolean isDividedBy(int n, int count) {
        if (count == 1) {
            return squareNumber.contains(n);
        }
        for (int sqr : squareNumber) {
            if (isDividedBy(n - sqr, count - 1)) {
                return true;
            }
        }
        return false;
    }
}