Leetcode279. Perfect Squares

題目：https://leetcode.com/problems/perfect-squares/description/

思路：一開始想說，如果給定n，那也許扣掉比n小的最大perfect num，持續做下去會是答案，但發現20=16+1+1+1+1=9+9+2，所以greedy應該無法。應該要把所有的可能都跑過一次，題目給的n<= 10^4，應該不可以太過暴力解，所以可以思考看看dp。

假設dp[n]是答案的話，那dp[n] = min(dp[n-num] for num in perfectNums)。
照這個做法就能做出來。

後來看了討論區發現這不是最好的解法，最好的解法是數學解，所以做個筆記記錄一下。

主要定理：Lagrange's four-square theorem
這個定理是在說，所有的自然數都可以被表達四個整數平方和的相加，所以答案最多就是4，但答案也可能是1, 2, 3。如果是1 那直接for loop 判斷就好，如果是2, 3的話，需要其他定理來幫忙。
對於2的狀況：使用費馬平方和定理，這個定理是說，一個整數可以寫成兩個整數平方和，充分必要這個數字除四餘一。
對於3的狀況：使用Legendre's three-square theorem，這個定理說，如果一個數可以寫成三個整數的平方和，充分必要n = 4^a(8b + 7) 。

結論：這題可以拆成三步
1.判斷是不是perfect square
2.判斷是不是平方和
3.判斷是不是three-square還是four-square
complexity: Time=O(sqrt(n)), space=O(1)