力扣279题：完全平方数

力扣279题：完全平方数

题目描述

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

输入输出样例

输入：n = 12
输出：3 
解释：12 = 4 + 4 + 4
1
2
3

输入：n = 13
输出：2
解释：13 = 4 + 9
1
2
3

解法一，使用动态规划的思想

//建立的是完全平方数，可以使用动态规划的思想进行解题
    int numSquares(int n)
    {
        vector<int>dp(n+1);

        //先初始化最低的值，即都为1组成的
        for(int i=0;i<=n;i++)
        {
            //初始化
            dp[i]=i;

//设定状态转移方程
//状态转移方程的推导可以理解将当前值，跟之前减去平方数的最小值进行比较。因为二者就是相差一个完全平方数，因此只需要在原来的基础上加上一就好了
            for(int j=1;j*j<=i;j++)
            {
                dp[i]=min(dp[i],dp[i-j*j]+1);
            }
        }

        return dp[n];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

解法二，使用DFS

int num=INT_MAX;
    //使用dfs深度优先进行搜索
    int numSquares2(int n)
    {
        dfs(n,0,0);
        return num;
    }

    void dfs(int n,int count,int sum)
    {
        //筛选次数，相当于取最小值
        //因为最差的情况是全部由一组成，所以一定可以跳出循环
        if(count>=num)
        {
            return;
        }

        //如果合计的结果刚好等于n,存储对当前的次数
        if(sum==n)
        {
            num=count;
        }

        //从最大的往下开始古查找
        for(int i=sqrt(n-sum);i>=1;i--)
        {
            dfs(n,count+1,sum+i*i);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

解法三，使用BFS

int numSquares3(int n)
    {
        queue<int>que;
        
        //首先将第一次的搜索放入队列中
        for(int i=sqrt(n);i>=1;i--)
        {
            if(n-i*i==0)
            {
                return 1;
            }
            else{
                //将剩余的数字和剩余的次数入队
                que.push(n-i*i);
                que.push(1);
            }
        }

        while(true)
        {
            //保存队列的首元素
            int sum=que.front();
            que.pop();

            int count=que.front();
            que.pop();

            //从大到小进行搜索
            for(int i=sqrt(sum);i>=1;i--)
            {
                if(sum-i*i==0)
                {
                    return count+1;
                }
                else{
                    que.push(sum-i*i);
                    que.push(count+1);
                }
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41