[Leetcode] 279. Perfect Squares | 完全平方数

yPhantom 2020年02月08日 19次浏览

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

Example 1:

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

Example 2:

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

这题让找出最少的能组成给定n的perfect square的个数。

之所以记录这道题呢,是因为我觉得这道题的整个分析过程比较经典。一开始看见这个问题,也想不出什么巧妙的方法,那就直接采用最native最直接的方法呗。

暴力法

class Solution {
    public int numSquares(int n) {
        if (n == 0) {
            return 0;
        }
        if ((int) Math.sqrt(n) == 1) {
            return n;
        }
        int start = (int) Math.sqrt(n);
        int res = n;
        for (int i = start; i >= 1; i--) {
            res = Math.min(res, numSquares(n - i * i) + 1);
        }
        return res;
    }
}

直接采用最直接的递归。果不其然超时了。当n等于55的时候还能过,等于56的时候就TLE了。

怎么办呢,以前做题的时候对于这种递归解法常常加一个HashMap来避免重复计算,对于我的上述解法而言,例如n=12,结果应该是3,4+4+4嘛。那么在第一次我们计算出了4的numSquares值后,就将4保存下来,避免后续重复计算4的numSquares值。

HashMap剪枝

class Solution {
    public int numSquares(int n) {
        return helper(n, new HashMap<>());
    }
    
    private int helper(int n, Map<Integer, Integer> map) {
        if (n == 0) {
            return 0;
        }
        if (map.containsKey(n)) {
            return map.get(n);
        }
        if ((int) Math.sqrt(n) == 1) {
            return n;
        }
        int start = (int) Math.sqrt(n);
        int res = n;
        for (int i = start; i >= 1; i--) {
            res = Math.min(res, helper(n - i * i, map) + 1);
        }
        map.put(n, res);
        return res;
    }
}

这样确实过了,但是效率极低。

Runtime: 567 ms, faster than 5.02% of Java online submissions for Perfect Squares.
Memory Usage: 45.4 MB, less than 13.89% of Java online submissions for Perfect Squares.

花了567ms,只超过了5.02%。

这个时候仔细分析下,发现这道题似乎表现出了“最优子结构”的动态,是不是可以用动态规划呢?

最优体现在最小值,子结构体现在整体可以由部分组合而成。

动态规划

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