完全平方数

题目描述：

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例 1：

输入：n = 12
输出：3
解释：12 = 4 + 4 + 4
示例 2：

输入：n = 13
输出：2
解释：13 = 4 + 9

提示：

1 <= n <= 104

思路:

动态规划 d p[i] = min(dp[i-j*j]……)+1

代码:

func numSquares(n int) int {
    dp := make([]int, n+1)
    dp[0] = 0
   
    for i:=1;i<=n;i++{
        minNum := 9999
        for j:=1;i>=j*j;j++{
            minNum = min(minNum, dp[i-j*j])
        }
        if minNum!= 9999{
            dp[i] = minNum+1
        }
    }
    // fmt.Println(dp)
    return dp[n]
}

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

代码效率：

执行用时：20 ms, 在所有 Go 提交中击败了86.13%的用户
内存消耗：6.1 MB, 在所有 Go 提交中击败了90.94%的用户