279.md

Perfect Squares

题目

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

Example 1: Input: n = 12 Output: 3 Explanation: 12 = 4 + 4 + 4.

Example 2: Input: n = 13 Output: 2 Explanation: 13 = 4 + 9.

思路

总结：
    bfs：对于某个n而言，结果有可能是使用了重复的square组成。所以从能使用的最大的squares开始使用(从1开始不合理，因为从1开始几乎是不可能是least的)。
part1:
    先生成一个squares数组存放[1,4,9,16...x0,x1,x2] x2 < n
part2：
    广度优先遍历：指从x2开始往前尝试，优先重复使用某个数(广度)。
注意：
    剪枝：如果当前使用的square数量比之前计算得出的min要大的话就可以结束使用了当前这些square的各种可能了。

代码

//bfs
func numSquares(n int) int {
    squares := []int{}
    for i := 1; i*i <= n ; i++ {
        squares = append(squares, i*i)
        if squares[i-1] == n {
            return 1
        }
    }
    min := math.MaxInt64
    bfs(squares, n, len(squares)-1, 0, &min)
    return min
}

func bfs(squares []int, n, index, curMin int, min *int) {
    if n == 0 {
        if curMin < *min {
            *min = curMin
        }
        return
    }
    for i := index; i >= 0; i-- {
        if n - squares[i] < 0 {
            continue
        }
        if curMin+1 > *min || *min == 2 {
            return
        }
        bfs(squares, n-squares[i], i, curMin+1, min)
    }
}

//dp
func numSquares(n int) int {
    dp := make([]int, n)
    square := 1
    squareNums := make(map[int]struct{}, 0)
    for i := 1 ; i <= n; i++ {
        square = i * i
        if square > n {
            break
        }
        squareNums[square] = struct{}{}
    }
    for i := 0; i < len(dp); i++ {
        if _, ok := squareNums[i + 1]; ok {
            dp[i] = 1
            continue
        }
        for num, _ := range squareNums {
            if num > i + 1 {
                continue
            }
            if dp[i] == 0 || dp[i] > dp[i - num] + 1 {
                dp[i] = dp[i - num] + 1 
                if dp[i] == 2 {
                    break
                }
            }
        }
    }
    //fmt.Println(dp)
    return dp[n-1]
}