golang力扣leetcode 279.完全平方数

很明显，大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
}