⭐⭐⭐⭐⭐【BFS求最小次数】LeetCode 279. Perfect Squares

题目描述

知识点

BFS/动态规划

结果

实现

码前思考

1. 这是在一个微信公众号上看见的题目，对于求最小次数的问题，BFS由于具有与生俱来的层数，所以很容易在每层中进行判断，当满足条件时就是最小次数了！
2. 为了避免超时，一定要使用一个hash来存储已经处理过的数据，否则单纯的暴力一定会超时的

代码实现

//使用BFS进行求解，最小的数量就是首先减到0时的层数！
//可以设置一个小小的剪枝，设置一个vis数组
class Solution {
public:
    int numSquares(int n) {
        //首先获取小于n的所有平方数
        vector<int> snum;
        vector<bool> vis(n+1,false);
        for(int i=1;i*i<=n;i++){
            snum.push_back(i*i);
        }
        int len = snum.size();
        //接下来进行层序遍历
        queue<int> q;
        q.push(n);
        int level = -1;
        bool flag = true;
        while(flag){//内部终止循环
            level++;
            int size = q.size();
            for(int i=0;i<size;i++){
                int cur = q.front();
                q.pop();
                printf("%d %d\n",level,cur);
                if(cur==0){
                    flag = false;
                    break;
                }
                for(int j=0;j<len&&cur-snum[j]>=0;j++){
                    if(!vis[cur-snum[j]]){  //注意是入队就设置
                        q.push(cur-snum[j]);
                        vis[cur-snum[j]] = true;
                    }
                }
            }
        }
        return level;
    }
};

码后反思

1. 其实这道题目不一定要使用BFS，其实这道题目就是硬币找零的问题啊，典型的动态规划求解问题！看到最优的问题，还是要优先考虑动态规划，再去想其他。