完全平方数

1. 题目描述

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

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

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

2. 思路

• DFS：减枝+传入参数
• DFS+缓存：枚举+缓存+传出

3. 实现

3.1. DFS减枝

package main

import (
	"math"
)


func numSquares(n int) int {
	nums := make([]int, 0)
	for i := 1; i <= n; i++ {
		current := i * i
		if current <= n {
			nums = append(nums, current)
		}
	}

	min := math.MaxInt32
	size := 0
	numSquaresDFS(nums, len(nums)-1, n, &size, &min)
	return min
}

func numSquaresDFS(nums []int, index int, target int, size *int, min *int) {
	if target == 0 {
		*min = Min(*min, *size)
		return
	}

	for i := index; i >= 0; i-- {
		current := target - nums[i]
		if current >= 0 && *size+1 < *min {
			*size++
			numSquaresDFS(nums, i, current, size, min)
			*size--
		}

	}
}


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

3.2. DFS+缓存

func numSquares(n int) int {
    squares := make([]int, 0)
    for i := 1; i <= n; i++ {
        s := i * i
        if s > n {
            break
        }
        squares = append(squares, s)
    }

    memo := make(map[int]int, 0)
    count := numSquaresDFS(squares, n, memo)
    if count == math.MaxInt32 {
        return -1
    }
    return count
}

func numSquaresDFS(squares []int, target int, memo map[int]int) int {
    count, ok := memo[target]
    if ok {
        return count
    }

    if target < 0 {
        return math.MaxInt32
    }

    if target == 0 {
        return 0
    }

    count = math.MaxInt32
    for i:= 0; i < len(squares); i++ {
        count = min(count, numSquaresDFS(squares, target-squares[i], memo))
    }
    memo[target] = 1 + count
    return 1 + count

}

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

4. 参考

• 279. 完全平方数 - 力扣（LeetCode）