279.完全平方数

动态规划

dp[i] 表示和为i的完全平方数的最少数量。则可以得到状态转移方程： dp[i] = min(dp[i-j^2]) + 1 。

时间复杂度： O(N√N)。状态转移的时间复杂度为O(√N)，攻击N个状态。
空间复杂度：O(N)

func numSquares(n int) int {
    // dp[i] = min(dp[i-j^2]) + 1

    dp := make([]int, n+1)
    for i := 1; i <= n; i++{
        minDp := math.MaxInt
        for j := 1; j*j <= i; j++ {
            minDp = min(minDp, dp[i-j*j])
        }
        dp[i] = minDp + 1
    }

    return dp[n]
}

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