题目
Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, …) which sum to n.
描述
给定一个数n,求最少需要多少个完全平方数求和能得到n；完全平方数为1,4,9,16…
例子
Input: n = 13 Output: 2 Explanation: 13 = 4 + 9.
解法
使用动态规划来做，对于每个数，都可以看成一个完全平方数+一个普通数，如dp[12]=dp[9]+dp[3],dp[12]=dp[8]+dp[4]
dp[17]=dp[16]+dp[1],所以对每个数i，找出dp[i-j*j]+1,dp[i-j*j]就是普通数的最少平方和个数，这样就可遍历j，找出最小值即可
代码
const MAX = 999999999
func numSquares(n int) int {
dp := make([]int,n+1,n+1)
for i:=1;i<=n;i++{
dp[i]=MAX
}
dp[0]=0
for i:=1;i<=n;i++{
for j:=0;j*j<=i;j++{
dp[i]=Min(dp[i-j*j]+1,dp[i])
}
}
return dp[n]
}
func Min(x, y int) int {
if x < y {
return x
}
return y
}
总结
虽然知道使用动态规划做，但是无法分析出这道题的状态转移方程式怎么样的，没能想到每个数最少的情况是由一个完全平方数+一个普通数。
