兩種都是動態規劃的方法，但第一種比較暴力和愚蠢，第二種利用了完全平方數。

方法一：無腦動態規劃，會超時

解題思路：

利用一維數組存儲 n 個整數的結果。

首先要判斷 i 是不是 就是一個完全平方數，如果是，那就不用循環遍歷后面的狀態轉移方程了，dp[i] = 1即可。

當 i 不是完全平方數時，狀態轉移方程為 dp[i] = min(dp[k] + dp[i - k])，找到最小的分割，就得到了最少完全平方數的個數。

但是會出現超時。

?

class Solution { public:int numSquares(int n) {vector<int> dp(n+1, 0);dp[1] = 1;if(n == 1) return dp[n];for(int i = 2; i <= n; i++){//要先判斷 i 是不是就是完全平方數int j = 1;bool flag = false;while(j * j <= i){if(j * j == i){dp[i] = 1;flag = true;break;}j++;}if(flag) continue;// n 不是完全平方數int minnum = i;for(int k = 1; k < i/2 + 1; k++){if(dp[k] + dp[i - k] < minnum){minnum = dp[k] + dp[i - k];}}dp[i] = minnum;}return dp[n];} };

?

方法二：

解題思路：

自底向上(自小向大)更新 動態數組 dp。狀態轉移方程為 dp[i + j * j] = min( dp[i + j * j], dp[i] + 1) 。

舉例如下，如果輸入的 n = 12，則更新順序為：

dp[0]?--> dp[0 + 1*1] = dp[1] --> dp[0 + 2*2] = dp[4] --> dp[0 + 3*3] = dp[9]

dp[1] --> dp[1 + 1*1] = dp[2] --> dp[1 + 2*2] = dp[5] --> dp[1 + 3*3] = dp[10]

dp[2] --> dp[2 + 1*1] = dp[4] -->? ?……

……

?

class Solution { public:int numSquares(int n) {vector<int> dp(n+1, INT_MAX);dp[0] = 0;for(int i = 0; i <= n; i++){for(int j = 1; i + j * j <= n; j++){dp[i + j * j] = min(dp[i + j * j], dp[i] + 1);}}return dp.back();} };

?

?

?

總結

以上是生活随笔為你收集整理的Leetcode 279. 完全平方数 解题思路及C++实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。