本文共 3949 字，大约阅读时间需要 13 分钟。

原题目

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

示例 1:

输入: n = 12

输出: 3

解释: 12 = 4 + 4 + 4.

示例 2:

输入: n = 13

输出: 2

解释: 13 = 4 + 9.

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/perfect-squares

题目分析

方法一：

bfs广搜：next=cur-j*j

12
11						8			3
10			7		2	7	4		2
9	6	1	6	3	1		3	0

方法二：

动态规划 状态转移方程：dp[ i ]=fmin(dp[ i ],dp[i - j * j]) 方法三： 数学 四平方和定理（Lagrange’s four-square theorem） 说明每个正整数均可表示为4个整数的平方和。 先判断这个数是否满足 4^a*(8b+7)如果满足，那么这个数就至少需要 4 个数的平方和表示。 如果不满足，再在上面除以 4 之后的结果上暴力尝试只需要 1 个数就能表示和只需要 2 个数就能表示的情况。 如果还不满足，那么就只需要 3 个数就能表示。 一个比1大的整数能够被写成两个平方的和的形式，当且仅当它的素数分解中不包含这样的素数，该素数对4取余等于3且该素数的指数为奇数。

完整代码

方法一：

typedef struct QNode{       int data;    struct QNode *next;}QNode,*QueuePtr;typedef struct{       QueuePtr front;    QueuePtr rear;}LinkQueue;void InitQueue(LinkQueue *Q){       Q->rear=Q->front=(QueuePtr)malloc(sizeof(QNode));    Q->front->next=NULL;}void DestroyQueue(LinkQueue *Q){       QueuePtr p=Q->front;    while(p)    {           Q->front=p->next;        free(p);        p=Q->front;    }}void ClearQueue(LinkQueue *Q){       QueuePtr p=Q->front->next;    Q->rear=Q->front;    while(p)    {           Q->front=p->next;        free(p);        p=Q->front;    }}bool QueueEmpty(LinkQueue Q){       if(Q.front==Q.rear)        return true;    else         return false;}int QueueLength(LinkQueue Q){       int len=0;    while(Q.front!=Q.rear)    {           len++;        Q.front=Q.front->next;    }    return len;}void EnQueue(LinkQueue *Q,int e){       QueuePtr p=(QueuePtr)malloc(sizeof(QNode));    p->data=e;    p->next=NULL;    Q->rear->next=p;    Q->rear=p;}void DeQueue(LinkQueue *Q){       if(Q->rear==Q->front)return;    QueuePtr p;    p=Q->front->next;    Q->front->next=p->next;    if(p==Q->rear)Q->rear=Q->front;    free(p);}int GetHead(LinkQueue Q){       return Q.front->next->data;}void QueueTraverse(LinkQueue Q){       QueuePtr p=Q.front->next;    while(p)    {           printf("%d ",p->data);        p=p->next;    }    printf("\n");}int numSquares(int n){       int steps=0;    LinkQueue Q;    InitQueue(&Q);    EnQueue(&Q,n);    int *vis=(int *)malloc(sizeof(int)*(n+1));    memset(vis,0,sizeof(int)*(n+1));    while(!QueueEmpty(Q))    {           steps++;        int len=QueueLength(Q);//printf("%d %d\n",steps,len);        for(int i=0;i

方法二：

typedef struct QNode{       int data;    struct QNode *next;}QNode,*QueuePtr;typedef struct{       QueuePtr front;    QueuePtr rear;}LinkQueue;void InitQueue(LinkQueue *Q){       Q->rear=Q->front=(QueuePtr)malloc(sizeof(QNode));    Q->front->next=NULL;}void DestroyQueue(LinkQueue *Q){       QueuePtr p=Q->front;    while(p)    {           Q->front=p->next;        free(p);        p=Q->front;    }}void ClearQueue(LinkQueue *Q){       QueuePtr p=Q->front->next;    Q->rear=Q->front;    while(p)    {           Q->front=p->next;        free(p);        p=Q->front;    }}bool QueueEmpty(LinkQueue Q){       if(Q.front==Q.rear)        return true;    else         return false;}int QueueLength(LinkQueue Q){       int len=0;    while(Q.front!=Q.rear)    {           len++;        Q.front=Q.front->next;    }    return len;}void EnQueue(LinkQueue *Q,int e){       QueuePtr p=(QueuePtr)malloc(sizeof(QNode));    p->data=e;    p->next=NULL;    Q->rear->next=p;    Q->rear=p;}void DeQueue(LinkQueue *Q){       if(Q->rear==Q->front)return;    QueuePtr p;    p=Q->front->next;    Q->front->next=p->next;    if(p==Q->rear)Q->rear=Q->front;    free(p);}int GetHead(LinkQueue Q){       return Q.front->next->data;}void QueueTraverse(LinkQueue Q){       QueuePtr p=Q.front->next;    while(p)    {           printf("%d ",p->data);        p=p->next;    }    printf("\n");}int numSquares(int n){       int steps=0;    LinkQueue Q;    InitQueue(&Q);    EnQueue(&Q,n);    int *vis=(int *)malloc(sizeof(int)*(n+1));    memset(vis,0,sizeof(int)*(n+1));    while(!QueueEmpty(Q))    {           steps++;        int len=QueueLength(Q);//printf("%d %d\n",steps,len);        for(int i=0;i

方法三