Problem#
給你一個整數 n，回傳最少需要幾個完全平方數加起來等於它?
測資限制#
- $1 \le n \le 10^4$
想法#
令 $f(n)$ 為整數 $n$ 最少需要 $f(n)$ 個完全平方數: 可以思考每次可以挑 $1, 2, 4, \cdots, i^2 (i \in [1, 100])$ 這個完全平方數，所以 $f(n)$ 就等於 $f(n-i^2) + 1$，因為目標是要找最少需要幾個完全平方數，所以可以得出式子: $f(n) = \max_{1 \le i \le 100}(f(n-i^2)+1)$
AC Code#
- 時間複雜度: $\mathcal{O}(n \sqrt{n})$
- 空間複雜度: $\mathcal{O}(n)$
賞析#
TODO: 官方題解