perfect-squares.go

// https://leetcode.com/problems/perfect-squares

// 1 -> 1
// 2 -> 1 + 1
// 3 -> (1 + 1) + 1
// 4 -> 4
// 5 -> 4 + 1
// 6 -> 4 + 1 + 1
// 7 -> 4 + 1 + 1 + 1
// 8 -> 4 + 4
// 9 -> 9
// 10 -> 9 + 1
// 11 -> 9 + 1 + 1
// 12 -> 9 + 1 + 1 + 1 = 8 + 4 -> 4 + 4 + 4
// 13 -> 9 + 4

func numSquares(n int) int {
    dp := make([]int, n + 1)
    dp[0] = 0
    square := 0
    
    for i := 1; i <= n; i++ {
        nextSquare := (square + 1) * (square + 1)
        
        if i == nextSquare {
            dp[i] = 1
            square++
        } else {
            prevSquare := square * square
            dp[i] = dp[prevSquare] + dp[i - prevSquare]
            
            for prev := square - 1; prev > 0 && prev >= square / 2; prev-- {
                prevSquare := prev * prev
                dp[i] = min(dp[i], dp[prevSquare] + dp[i - prevSquare])
            }
        }
    }
    
    return dp[n]
}

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