如題：

給定正整數 n，找到若干個完全平方數（比如 1, 4, 9, 16, ...）使得它們的和等于 n。你需要讓組成和的完全平方數的個數最少。示例?1: 輸入: n = 12 輸出: 3 解釋: 12 = 4 + 4 + 4.示例 2: 輸入: n = 13 輸出: 2 解釋: 13 = 4 + 9.

這道題和leetcode 752. 打開轉盤鎖類似，都可以使用廣度優先搜索來求解。大體思路都是根據遍歷當前節點的子節點，尋找目標解的過程，類似題目做多了，就比較容易了。

這道題可以看作從根節點0出發，往下搜索子節點，找到匹配則返回深度即可，相當于最短路徑，當然是廣度優先搜索BFS。
每層節點的子節點分別為父節點加上(1, 4, 9, 16....(i^2 < n) )。使用隊列存儲節點，每次遍歷前先獲取當層節點數，即隊列長度。然后依次遍歷該節點子節點，如果長度符合則返回，不符合且是第一次訪問，則添加到隊列中去，如果已經訪問過，則不需要添加。需要額外的哈希數組，用來存儲訪問過的元素，隊列和哈希數組總共需要額外的2N的空間。bfs搜索方法協同隊列的使用代碼框架比較固定，往往可以共用一套代碼。下面是本題的圖示：

c語言代碼如下，前面部分代碼是關于隊列實現的，可以略過不看，僅看最后的bfs搜索部分即可。

/* BFS */typedef struct {int length, max;int front, rear;int *sq; } queue;//創建隊列 queue* queueCreate(int k) {queue* a;if (k < 0)return NULL;elsea = (queue*) malloc(sizeof(queue));if (!a)return NULL;else{a->max = k+1;a->length = a->front = a->rear = 0;a->sq = (int *)malloc(sizeof(int) * (k+1));if (!a->sq){free(a);return NULL;}return a;} }//入隊列 int enQueue(queue* obj, int value) {if (obj->length == (obj->max - 1))return 0;else{obj->sq[obj->rear] = value;obj->rear = (obj->rear + 1) % obj->max;obj->length++;}return 1; }//出隊列 int deQueue(queue* obj) {int head;if (obj->front == obj->rear)return 0;else{head= obj->front;obj->front = (obj->front + 1) % obj->max;obj->length--;return obj->sq[head];} }//獲取當前隊列長度 int queueLength(queue *obj) {return obj->length; }//判斷隊列是否為空 int isEmpty(queue* obj) {if (obj->front == obj->rear)return 1;elsereturn 0; }//判斷隊列是否滿 int isFull(queue* obj) {if (obj->length == obj->max - 1)return 1;elsereturn 0; }//釋放隊列 void queueFree(queue* obj) {free(obj->sq);free(obj);return; }int numSquares(int n){int i,j,next, curr, size, steps = 0, *visited;queue *q;if (n == 0 || n == 1)return n;q = queueCreate(n + 1);visited = (int *)malloc(sizeof(int) * (n+1));for (i = 0; i <= n; i++)visited[i] = 0;enQueue(q, 0);visited[0] = 1;while(!isEmpty(q)){//深度遞增steps++;size = queueLength(q);for (i = 0; i < size; i++){//遍歷子節點curr = deQueue(q);for (j = 1; j * j <= n; j++){next = curr + j*j;if (next == n) return steps;if (next > n) break;if (visited[next]) continue;//加入到隊列，以待訪問其子節點visited[next] = 1;enQueue(q, next);}}}queueFree(q);free(visited);return steps; }

第二種方法是使用一維動態規劃，設dp[i] 為總和為i所需要最少的平方數。狀態遷移方程為：

dp[i] = MIN(dp[i], dp[i - j * j] + 1);

邊界為b[ i * i ] = 1；雖說這道題很明顯能夠看出動態規劃的痕跡，不過我還是沒能找到狀態遷移方程，還是需要多思考。動態規劃寫的代碼比較簡潔。下面是c代碼：

#define MIN(a,b) ((a) > (b) ? (b) : (a))int numSquares(int n){int i, j, k, *dp;if (n < 2)return n;dp = (int *)malloc(sizeof(int) * (n+1));if (!dp) exit(1);for (i = 0; i <= n; i++)dp[i] = INT_MAX;//初始化for (i = 1; i * i <= n; i++)dp[i*i] = 1;//狀態遷移for (i = 1; i <= n; i++){for (j = 1; j * j < i; j++)dp[i] = MIN(dp[i], dp[i - j * j] + 1);}return dp[n]; }

=============================================================================================

Linux應用程序、內核、驅動開發交流討論群(745510310)，感興趣的同學可以加群討論、交流、資料查找等，前進的道路上，你不是一個人奧^_^。

總結

以上是生活随笔為你收集整理的leetcode 279. 完全平方数 bfs广度优先解法 图解 动态规划解法 c代码的全部內容，希望文章能夠幫你解決所遇到的問題。

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