完全平方数-中等

难度：中等

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于* n*。你需要让组成和的完全平方数的个数最少。

示例：

输入: n = 12;
输出: 3;
解释: 12 = 4 + 4 + 4;

1
2
3

解题思路：
时间复杂度：O(n\sqrt{n}n)
空间复杂度：O(n)
思路
状态定义：dp[i]：表示当前数字i最少有几个平方数构成
转移方程：dp[i] = min(dp[i],dp[i - j*j] + 1) ```javascript var numSquares = function(n) { let dp = new Array(n+1).fill(0); for(let i = 1;i <= n;i++){ dp[i] = i; for(let j = 1;j*j <= i;j++){ dp[i] = Math.min(dp[i],dp[i - j*j] + 1); } } return dp[n]; }; ```

BFS

var numSquares = function (n) {
  let queue = [n];
  let visited = {};
  let level = 0;
  while (queue.length > 0) {
    // 层序遍历
    level++;
    let len = queue.length;
    for (let i = 0; i < len; i++) {
      let cur = queue.pop();
      for (let j = 1; j * j <= cur; j++) {
        let tmp = cur - j * j;
        // 找到答案
        if (tmp === 0) {
          return level;
        }
        if (!visited[tmp]) {
          queue.unshift(tmp);
          visited[tmp] = true;
        }
      }
    }
  }
  return level;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

← 不同路径-中等乘积最大子数组-中等 →

# 完全平方数-中等

完全平方数-中等