給定正整數(shù) n，找到若干個完全平方數(shù)（比如 1, 4, 9, 16, ...）使得它們的和等于 n。你需要讓組成和的完全平方數(shù)的個數(shù)最少。

解題思路
BFS解法，干凈利落。
起初我想不通為什么用BFS,這題與BFS又有什么關系，相信很多刷題量不是很多的朋友也會有同樣的困惑。
我們可以先刻意的把這題往BFS上靠，然后等越靠越近的時候，你就慢慢有感覺了，就會明白與BFS的微妙關系了，具體又該怎么靠呢？
還記得我們初次接觸BFS，是在層序遍歷樹的時候，遍歷樹的時候，首先會不會得從根節(jié)點出發(fā)，層層遍歷，沒見過從最底層節(jié)點開始層序遍歷這種玩法把？

BFS建模
那么放在本題，既然要用BFS, 肯定得找一個根節(jié)點，這個根節(jié)點就是題目給的數(shù)字 n，然后我們的目標就是 [搜索]，將n 變成 0 的最短步數(shù)（可以理解每遍歷一層就相當于走了一步）。到這里你可能腦海中還是沒有樹的形狀，主要原因在于你現(xiàn)在腦海中的 n 是個比較小的數(shù)字，所以構建不出樹的形狀，比如 n=4，它本身就是完全平方數(shù)，自然就不能很好的擴散出樹的形狀，這時候 我們 可以把 n 取一個不大不小的數(shù)字 12.

641036134c746b8bba3be26299a9cbd8493950dba92edcf50408031903c4f37c.jpg

class Solution { 
    public int numSquares(int n) { 
          Queue<int[]> queue = new LinkedList<>(); 
          boolean[] vis = new boolean[n+1]; //int數(shù)組的第一個數(shù)字表示的是當前的數(shù)字，第二個數(shù)字表示，需要走幾步才能到達數(shù)字n 
         //因為是從根節(jié)點 n 開始遍歷的，所以我一上來就能訪問到 n，即可直接到達n, 走0步即可。 
          queue.add(new int[]{n,0}); 
          vis[n] = true; 
          while(!queue.isEmpty()) { 
         int size = queue.size(); 
        for(int i = 0; i < size; i++) { 
             int[] cur = queue.poll(); 
            if(cur[0] == 0) return cur[1]; 
          //這個循環(huán)是精華所在，作用就是將13 依次分割成12 9 4 
         for(int j = 1; ; j++) { 
            int a = cur[0] - j*j; if(a < 0) break; 
            if(a == 0) 
              return cur[1] + 1; 
           if(!vis[a]) { 
           //為什么步數(shù)+1 ？因為我當前數(shù)字a,比如是9，我可以由 13-4分割而來，并且4是一個完全平方數(shù)，這個-4就說明走了一步， 所以+1 
        queue.add(new int[]{a, cur[1] + 1}); vis[a] = true; } } } } return -1; } }