279. 完全平方数

要求：找最少完全平方数使和为n
思路：
法一：最少可以理解为最短路径，节点n到节点0，中间相邻两个节点的差等于完全平方数，第一层是n，设(int)sqrt(n)=sn，则n的下一层是n-sn^2，n-(sn-1)平方，…n-1平方。同理第三层是第二层每个节点减去相应的平方
但是如果每一层都放进所有元素会超时，要记录visited，因为元素相同记一个就行了，从那个开始下降

class Solution {
public:
    int numSquares(int n) {
        queue q;
        unordered_map visited;
        q.push(n);
        int level=0;
        while(!q.empty()){
            int levelsize=q.size();
            ++level;
            while(levelsize--){
                int tmp=q.front();
                q.pop();
                if(tmp==0)return level-1;
                for(int i=(int)sqrt(tmp);i>=1;--i){
                    int ttmp=tmp-i*i;
                    if(visited.count(ttmp)==0){
                        q.push(ttmp);
                        visited[ttmp]=1;
                    }
                }
            }
        }
        return level-1;
    }
};

法二：动态规划，还没做到