LeetCode 279. Perfect Squares

Problem

LeetCode 279. Perfect Squares

1. 题目简述

给出一个正整数n，找出最少的能够组成n的完全平方数的个数。例如：

Example 1:
Input: n = 12
Output: 3 
Explanation: 12 = 4 + 4 + 4.

Example 2:
Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

Note:

最坏情况就是全都由1来组成，例如 3 = 1 + 1 + 1

2. 算法思路

参考链接：LeetCode 5种解法

其实讲道理，这道题的解法看得我头昏眼花，这里暂时只讲dp解法，关于greedy，BFS和math方法，后面有空再看，待完善。

DP

首先，我们先计算sqrt(n)，向下取整为x，那么1到x都是我们的备选区间，然后我们从1到x进行遍历，找到最少的需要的数量（从后向前遍历不一定是最小值，例如：12 = 9 + 1 + 1 + 1，但是最少的是12 = 4 + 4 + 4）。我们用一个dp数组来记录当前的最小值即可，减少遍历次数。

时间复杂度为O(n * 根号n)。

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        findNumSquares(n, dp);

        return dp[n];
    }

    private int findNumSquares(int n, int[] dp) {
        if (dp[n] != 0) {
            return dp[n];
        }

        if (n <= 1) {
            dp[n] = n;
            return n;
        }

        int res = n;
        // dp值为0，说明从未找过；dp值大于0，即为解；最差情况就全是1喽
        int max = (int)Math.floor(Math.sqrt((double)n));
        for (int i = 1; i <= max; i++) {
            res = Math.min(res, findNumSquares(n - i * i, dp) + 1);
        }

        dp[n] = res;

        return res;
    }
}