# 279 Perfect Squares

給一個整數n，問最少幾個prefect squared number可以加總為n?

• 思路

舉個例子觀察自己是怎麼思考的，

首先我把squared number直接標成1，

那我在算2的時候，會先把1（距離2最近的perfect squared）扣掉，再看dp[1]是多少，所以得到1+1 = 2

其他數字的計算也同理

例如: 7 = dp[4] + dp[3] = 1 + 3

所以我想用一個dp陣列，和一個儲存perfect squares的list來解題。

• pseudo code

          a list to keep perfect squared numbers
          an array to record all numbers and their least number of perfect squared numbers
          for i=1:n
              if i is perfect squared,
                  add i to list,
                  array[i] = 1
              else
                  go through list j
                      min
                      if array[j] + array[i-j]
                          update min
                  array[i] = min
  
          return array[n-1]
  

• Code

  public class Solution {
      public int numSquares(int n) {
          List<Integer> perfectSquared = new ArrayList<>();
          int[] dp = new int[n+1];
          dp[0] = 0;
          dp[1] = 1;
          perfectSquared.add(1);
          for(int i=2; i<n+1; i++){
              if(isPerfectSquared(i)){
                  perfectSquared.add(i);
                  dp[i] = 1;
              }else{
                  int min = Integer.MAX_VALUE;
                  for(int j=0; j < perfectSquared.size(); j++){
                      int k = perfectSquared.get(j);
                      if(dp[k] + dp[i-k] < min){
                          min = dp[k] + dp[i-k];
                      }
                  }
                  dp[i] = min;
              }
              //System.out.println(dp[i]);
          }
  
          return dp[n];
      }
  
      private boolean isPerfectSquared(int i){
          if((int)Math.sqrt(i) == Math.sqrt((double)i) )  return true;
          return false;
      }
  }
  

• 分析：
  這個做法時間複雜度是O(n*n^(1/2)) = O(n^(3/2)) 空間用了額外的n^(1/2)
  想要更優化最好可以不用另外用List存perfect squared numbers。
  參考此作法

public int numSquares(int n) {
    int[] dp = new int[n + 1];
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0] = 0;
    for(int i = 1; i <= n; ++i) {
        int min = Integer.MAX_VALUE;
        int j = 1;
        while(i - j*j >= 0) {
            min = Math.min(min, dp[i - j*j] + 1);
            ++j;
        }
        dp[i] = min;
    }        
    return dp[n];
}

• 超優化寫法： Based on Legendre's three-square theorem, 所有數字都可以寫成3個perfect square的總和, 除非他可以表示成4^a(8b+7)

class Solution {
    public int numSquares(int n) {
        while (n % 4 == 0)
            n /= 4;
        if (n % 8 == 7)
            return 4;
        for (int a=0; a*a<=n; ++a) {
            int b = (int) Math.sqrt(n - a*a);
            if (a*a + b*b == n)
                return a == 0 ? 1 : 2;
        }
        return 3;
    }
}