279.M 完全平方数

Problem: 279. 完全平方数

思路

动态规划。

设dp[i]为i的完全平方数的最少数量，则：

dp[i] = 1 + dp[i - j * j], 对于 j ∈ [1, j^(1/2)]

Code

import "math"

func numSquares(n int) int {
	dp := make([]int, n+1)
	for i := 1; i <= n; i++ {
		minPart := math.MaxInt
		for j := 1; j*j <= i; j++ {
			minPart = min(minPart, dp[i-j*j])
		}
		dp[i] = minPart + 1
	}

	return dp[n]
}

func min(a, b int) int {
	if a < b {
		return a
	}

	return b
}