0279. 完全平方数
题目地址(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.前置知识
递归
动态规划
公司
阿里
百度
字节
思路
直接递归处理即可，但是这种暴力的解法很容易超时。如果你把递归的过程化成一棵树的话（其实就是递归树）， 可以看出中间有很多重复的计算。
如果能将重复的计算缓存下来，说不定能够解决时间复杂度太高的问题。
递归对内存的要求也很高， 如果数字非常大，也会面临爆栈的风险，将递归转化为循环可以解决。
递归 + 缓存的方式代码如下：
const mapper = {};function d(n, level) { if (n === 0) return level; let i = 1; const arr = []; while (n - i * i >= 0) { const hit = mapper[n - i * i]; if (hit) { arr.push(hit + level); } else { const depth = d(n - i * i, level + 1) - level; mapper[n - i * i] = depth; arr.push(depth + level); } i++; } return Math.min(...arr);}/** * @param {number} n * @return {number} */var numSquares = function (n) { return d(n, 0);};如果使用 DP，其实本质上和递归 + 缓存 差不多。
DP 的代码见代码区。
关键点解析
如果用递归 + 缓存， 缓存的设计很重要 我的做法是 key 就是 n，value 是以 n 为起点，到达底端的深度。 下次取出缓存的时候用当前的 level + 存的深度 就是我们想要的 level.
使用动态规划的核心点还是选和不选的问题
for (let i = 1; i <= n; i++) { for (let j = 1; j * j <= i; j++) { // 不选（dp[i]） 还是 选（dp[i - j * j]） dp[i] = Math.min(dp[i], dp[i - j * j] + 1); }}代码
代码支持：CPP，JS
CPP Code:
class Solution {public: int numSquares(int n) { static vector<int> dp{0}; while (dp.size() <= n) { int m = dp.size(), minVal = INT_MAX; for (int i = 1; i * i <= m; ++i) minVal = min(minVal, 1 + dp[m - i * i]); dp.push_back(minVal); } return dp[n]; }};JS Code:
/** * @param {number} n * @return {number} */var numSquares = function (n) { if (n <= 0) { return 0; } const dp = Array(n + 1).fill(Number.MAX_VALUE); dp[0] = 0; for (let i = 1; i <= n; i++) { for (let j = 1; j * j <= i; j++) { // 不选（dp[i]） 还是 选（dp[i - j * j]） dp[i] = Math.min(dp[i], dp[i - j * j] + 1); } } return dp[n];};复杂度分析
时间复杂度：$O(N^2)$
空间复杂度：$O(N)$
大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
最后更新于
这有帮助吗？