golang力扣leetcode 279.完全平方数

• 279.完全平方数
• 题解
• 代码

279.完全平方数

题目：给一个n，问n最少由几个平方数相加得到

思路：

很明显，大n的值由小n推导过来，比如8=4+4，所以这里用dp
dp[i]:表示i最少由多少个平方数相加得到
dp[i-j*j]就是小n的值，则因为减去了j*j
所以dp[i]默认为1的原因就是默认其中一个平方数就是j*j

func numSquares(n int) int {
	dp := make([]int, n+1)
	for i := 1; i <= n; i++ {
		cnt := math.MaxInt32
		for j := 1; j*j <= i; j++ {
			cnt = min(cnt, dp[i-j*j])
		}
		dp[i] = cnt + 1
	}
	return dp[n]
}
func min(i, j int) int {
	if i > j {
		return j
	}
	return i
}