題目: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)