LeetCode 279. 完全平方数

https://leetcode-cn.com/problems/perfect-squares/

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

示例 1:

输入: n = 12

输出: 3

解释: 12 = 4 + 4 + 4.

示例 2:

输入: n = 13

输出: 2

解释: 13 = 4 + 9.

解法1：递归 + 记忆数组

  对于一个正整数数 n，我们需要找出它的最少完全平方数的组合个数。

  首先考虑 n <= 3 的情况，这种情况下，最小的完全平方数就只有 1，因此 n 的完全平方组合个数就是 n。

  然后来看 n >= 4 的情况，能够组成这个数的最大完全平方数很容易想到，就是 n 的平方根取整后的值，即： s = Math.floor(Math.sqrt(n)) ，假设这个值是 n 的组成数的其中一个，那剩下我们再对 n - s 做同样考虑即可。

  穷举所有情况， [2, s] (s 为 n 的平方根取整后的值)，直到当前的 n 小于等于 3 时，返回 n。

  使用图来表示就是：

image-20210104185104232

  不过对于一些比较大的数字，我们在计算过程其实是会有很多重复计算的（因为我们使用了穷举），也就是假设一个数字 n，它的根号取整值是 s，我们最开始枚举 s * s 是 n 的组合数之一，然后计算包含 s^2 的组合数个数时，我们遇到了数字 x1,x2,x3 之后计算得到了组合数个数，我们再回到开头，继续枚举 (s-1) * (s-1) 作为 n 的组合数之一，在这个计算过程中，我们遇到了数字 y1,y2,x2,x3 之后得到了结果。那么在这个过程中，我们的 x2,x3 就是重复计算的数。

  因此我们完全可以使用一个记忆数组 memeo 来根据当前的数字 n 记录 n 能够得到的最少的组合数，这样，当我们第二次遇到 x2 的时候，就能够凭借记忆数组直接返回 memo[x2]，减少了我们的计算。

JS 代码：

var numSquares = function(n) {
    let memo = [];

    const getCount = (num) => {
        if (num <= 3) {
            return num;
        }
		
        // 若已计算过，直接返回
        if (memo[num]) {
            return memo[num];
        }

        let sqrt = Math.floor(Math.sqrt(num));
        for (let i = sqrt; i >= 2; i--) {
            let c = getCount(num - i * i);
            // memo 记录 num 的最少的组合数个数
            memo[num] = Math.min(memo[num] || Number.MAX_VALUE, c + 1);
        }

        return memo[num];
    };

    return getCount(n);
};

 目录