leetcode-go/medium/279.perfect-squares.go

func numSquares(n int) int {
	dp := make([]int, n+1)
	dp[0] = 1000000
	for i := 1; i < n+1; i *= 2 {
		copy(dp[i:], dp[:i])
	}
	for i := 1; i*i <= n; i++ {
		dp[i*i] = 1
	}
	for i := 1; i < n; i++ { // n(k) = n(i + j*j) = n(i) + 1
		for j := 1; i+j*j <= n; j++ {
			if dp[i]+1 < dp[i+j*j] {
				dp[i+j*j] = dp[i] + 1
			}
		}
	}
	return dp[n]
}