279. 完全平方数

279. 完全平方数

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。
输入：n = 13
输出：2
解释：13 = 4 + 9

//完全背包问题，自顶向下=爬楼梯  时间n*根号n，空间On  
func numSquares(amount int) int {
    dp := make([]int ,amount + 1)
    dp[0] = 0
    //明确第一个循环，取的是 0-amount 的最小平方数个数，遍历平方和,最坏情况是都用1来组成;  
    //第二个循环求每层+累加 i的最小平方数个数=dp[amount]
    for i := 1; i <= amount; i++ {      //amount 需要的钱大小
        dp[i] = amount + 1         //边界条件，最大可能值，总的值+1，反正取个最大的完事，从最大开始缩写
        //dp[i] = math.MaxInt32
        for coin := 0; coin * coin <= i; coin++ {
            dp[i] = min(dp[i], dp[i - coin * coin ] + 1)     //核心，状态转移方程== 函数表达式
        }
    }
    return dp[amount]
}
func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}