LeetCode--279. 完全平方数【动态规划】
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 []int
for i := 1; i <= 10*n/i; i++ {
nums = append(nums, i*i)
}
//计算
for i := 1; i <= n; i++ {
minn := 1000
for 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
}