LeetCode279——完全平方数-蒲公英云

LeetCode279——完全平方数

我的LeetCode代码仓：https://github.com/617076674/LeetCode

原题链接：https://leetcode-cn.com/problems/perfect-squares/

题目描述：

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjMxOTI2_size_16_color_FFFFFF_t_70

知识点：广度优先搜索、动态规划

思路一：广度优先搜索

深搜用栈，广搜用队列。

时间复杂度是O(n ^ 2)。空间复杂度是O(n)。

JAVA代码：

class Solution {
    public int numSquares(int n) {
        int result = 1;
        Queue<Integer> queue = new LinkedList<>();
        queue.add(n);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int now = queue.poll();
                for (int j = 1; j * j <= now; j++) {
                    if (now - j * j == 0) {
                        return result;
                    }
                    queue.add(now - j * j);
                }
            }
            result++;
        }
        return -1;
    }
}

LeetCode解题报告：

思路二：动态规划

仔细分析思路一中的广搜算法：12可以由11加上1，或者是8加上4，或者是3加上9得到。

对于11可以由10加上1，或者是7加上4，或者是2加上9得到。

对于8可以由7加上1，或者是4加上4得到。

……如果更进一步分析下去，我们需要分析两次上述的7，这其实是一种重复计算，因此我们采用动态规划来进行优化。

状态定义：

f(x) ———— 数字总和为x的最少完全平方数个数

状态转移：

f(x) = min(f(x), 1 + f(y)), y∈[0, x - 1]，且x - y是一个完全平方数

时间复杂度是O(n ^ 1.5)。空间复杂度是O(n)。

JAVA代码：

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