279. 完全平方数
正文
题目
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
解释：给定一个整数，要求将它分解为a^2 + b^2 + c^2 + ...的形式
解决
抛开数学方法不提，这道题的突破口在于把整数 n 看成是 n - x^2 的形式，而这个数字必然小于 n 如此一来，便可以得出我们需要使用动态规划来解决，类似于背包问题，想到dp，这道题就比较简单了。
i每次+1，都需要根据之前的状态来更新，最后返回f[n]即可, 代码如下：
func numSquares(n int) int {f := make([]int, n+1)//预处理可能用到的平方集合var nums []intfor i := 1; i <= 10*n/i; i++ {nums = append(nums, i*i)}//计算for i := 1; i <= n; i++ {minn := 1000for j := 0; nums[j] <= i; j++ {minn = min(minn, f[i-nums[j]])}f[i] = minn + 1}return f[n]
}func min(a, b int) int {if a < b {return a}return b
}
