题解 | #最少的完全平方数#

package main

import (
	"fmt"
	"math"
)

func solution(n int) int {
	f := make([]int, n+1)
	for i := 1; i <= n; i++ {
		minNum := math.MaxInt
		for j := 1; j*j <= i; j++ {
			minNum = min(minNum, f[i-j*j])
		}
		f[i] = minNum + 1
	}
	return f[n]
}

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

/*
*
输入5
输出2
说明：1 + 2*2 = 5
*/
func main() {
	var n int
	fmt.Scan(&n)
	fmt.Println(solution(n))
}