0279. 完全平方数 #
标签:广度优先搜索,数学,动态规划
描述:给定一个正整数 n.从中找到若干个完全平方数(比如 1,4,1,16 ...),使得它们的和等于 n.
要求:返回和为 n 的完全平方数的最小数量.
输入:n = 12
解释:12 = 4 + 4 + 4
解释:13 = 4 + 9
暴力枚举思路:对于小于 n 的完全平方数,直接暴力枚举所有可能的组合,并且找到平方数个数最小的一个.
并且对于所有小于 $n$ 的完全平方数($k = 1, 4, 9, 16, ...$),存在公式:$ans(n) = min(ans(n - k) + 1),k = 1,4,9,16,...$
即: n 的完全平方数的最小数量 =