# 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 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。