# 0279. 完全平方数 ## 题目地址(279. 完全平方数) <https://leetcode-cn.com/problems/perfect-squares/> ## 题目描述 ``` <pre class="calibre18">``` 给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。 示例 1: 输入: n = 12 输出: 3 解释: 12 = 4 + 4 + 4. 示例 2: 输入: n = 13 输出: 2 解释: 13 = 4 + 9. ``` ``` ## 前置知识 - 递归 - 动态规划 ## 公司 - 阿里 - 百度 - 字节 ## 思路 直接递归处理即可，但是这种暴力的解法很容易超时。如果你把递归的过程化成一棵树的话（其实就是递归树）， 可以看出中间有很多重复的计算。 如果能将重复的计算缓存下来，说不定能够解决时间复杂度太高的问题。 > 递归对内存的要求也很高， 如果数字非常大，也会面临爆栈的风险，将递归转化为循环可以解决。 递归 + 缓存的方式代码如下： ``` <pre class="calibre18">``` <span class="hljs-keyword">const</span> mapper = {}; <span class="hljs-function"><span class="hljs-keyword">function</span> <span class="hljs-title">d</span>(<span class="hljs-params">n, level</span>) </span>{ <span class="hljs-keyword">if</span> (n === <span class="hljs-params">0</span>) <span class="hljs-keyword">return</span> level; <span class="hljs-keyword">let</span> i = <span class="hljs-params">1</span>; <span class="hljs-keyword">const</span> arr = []; <span class="hljs-keyword">while</span> (n - i * i >= <span class="hljs-params">0</span>) { <span class="hljs-keyword">const</span> hit = mapper[n - i * i]; <span class="hljs-keyword">if</span> (hit) { arr.push(hit + level); } <span class="hljs-keyword">else</span> { <span class="hljs-keyword">const</span> depth = d(n - i * i, level + <span class="hljs-params">1</span>) - level; mapper[n - i * i] = depth; arr.push(depth + level); } i++; } <span class="hljs-keyword">return</span> <span class="hljs-params">Math</span>.min(...arr); } <span class="hljs-title">/** * @param {number} n * @return {number} */</span> <span class="hljs-keyword">var</span> numSquares = <span class="hljs-function"><span class="hljs-keyword">function</span>(<span class="hljs-params">n</span>) </span>{ <span class="hljs-keyword">return</span> d(n, <span class="hljs-params">0</span>); }; ``` ``` 如果使用 DP，其实本质上和递归 + 缓存 差不多。 DP 的代码见代码区。 ## 关键点解析 - 如果用递归 + 缓存， 缓存的设计很重要 我的做法是 key 就是 n，value 是以 n 为起点，到达底端的深度。 下次取出缓存的时候用当前的 level + 存的深度 就是我们想要的 level. - 使用动态规划的核心点还是选和不选的问题 ``` <pre class="calibre18">``` <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = <span class="hljs-params">1</span>; i <= n; i++) { <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> j = <span class="hljs-params">1</span>; j * j <= i; j++) { <span class="hljs-title">// 不选（dp[i]） 还是 选（dp[i - j * j]）</span> dp[i] = <span class="hljs-params">Math</span>.min(dp[i], dp[i - j * j] + <span class="hljs-params">1</span>); } } ``` ``` ## 代码 ``` <pre class="calibre18">``` <span class="hljs-title">/** * @param {number} n * @return {number} */</span> <span class="hljs-keyword">var</span> numSquares = <span class="hljs-function"><span class="hljs-keyword">function</span>(<span class="hljs-params">n</span>) </span>{ <span class="hljs-keyword">if</span> (n <= <span class="hljs-params">0</span>) { <span class="hljs-keyword">return</span> <span class="hljs-params">0</span>; } <span class="hljs-keyword">const</span> dp = <span class="hljs-params">Array</span>(n + <span class="hljs-params">1</span>).fill(<span class="hljs-params">Number</span>.MAX_VALUE); dp[<span class="hljs-params">0</span>] = <span class="hljs-params">0</span>; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = <span class="hljs-params">1</span>; i <= n; i++) { <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> j = <span class="hljs-params">1</span>; j * j <= i; j++) { <span class="hljs-title">// 不选（dp[i]） 还是 选（dp[i - j * j]）</span> dp[i] = <span class="hljs-params">Math</span>.min(dp[i], dp[i - j * j] + <span class="hljs-params">1</span>); } } <span class="hljs-keyword">return</span> dp[n]; }; ``` ``` **复杂度分析** - 时间复杂度：O(N2)O(N^2)O(N2) - 空间复杂度：O(N)O(N)O(N) 大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：<https://github.com/azl397985856/leetcode> 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。