完全平方数

发表于 更新于 分类于 阅读次数：

完全平方数（难度：中等）

1

方法一：动态规划

dp[i]表示i最少可以由几个平方数构成。

初试化dp=[0,1,2,..., n]，长度为n+1，最多次数就是全由1构成。

遍历dp，对于i，遍历区间[1,n]：

​ 遍历所有平方数小于i的数j，遍历区间[1, sqrt(i)]

动态转移方程：

dp[i] = min(dp[i], dp[i - j * j]+1)，i表示当前数字，j*j表示平方数

复杂度

时间复杂度：O(n*sqrt(n))

空间复杂度：O(n)

代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n+1]; //dp[i]存放的是i最少可以由几个平方数构成， 初始化为[0,1,...,n]
        for(int i = 1; i <= n; i++){
            dp[i] = i;
            for(int j = 1; i-j*j >= 0; j++){
                dp[i] = Math.min(dp[i], dp[i-j*j]+1);
            }
        }
        return dp[n];
    }
}
2

方法二：广度优先搜索（BFS）

3