题目

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

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

 

示例 1：

输入：n = 12
输出：3 
解释：12 = 4 + 4 + 4
示例 2：

输入：n = 13
输出：2
解释：13 = 4 + 9
 
提示：

1 <= n <= 104

分析

首先分析一下，举个例子，对于数字 5，我们可以罗列出来它可能的情况：

4+1
3+2
2+3
1+4

并且我们在计算 数字5的时候，其实已经把数字 1-4 都计算过了，由此可以由前一个状态进行递推，所以这是一道动态规划的问题。

因为对于任何一个数 N，要探查其最小完全平方数和的数量，可以拆解为子问题：S(i)+S(N-i) 的最小和。i 为从1到 N-1 的数字，我们只需要从这些子问题中，筛选出和最小的即可。

S(N) = min(S(i)+S(N-i)) i为 1 至 N-1

题解

由此我们可以很容易的写出题解：

func numSquares2(n int) int {
	dp := make([]int, n+1)
	dp[1] = 1
	for i := 2; i <= n; i++ {
		_min := math.MaxInt
		for j := 1; j < i; j++ {
			if j*j == i {
				_min = 1
				break
			} else {
				_min = min(dp[j]+dp[i-j], _min)
			}
		}
		dp[i] = _min
	}
	return dp[n]
}

我们定义 dp数组，dp[i] 表示 i 的最小完全平方数和的数量，并且初始化状态为 dp[1]=1

之后从2开始，对于每一个 j， 我们计算 dp[j]+dp[i-j] 的最小值，并且在这个过程中，如果发现 i是一个完全平方数，那么其可以直接赋值为1。

但是观察代码不难发现，对于任意一个数，我们都需要从1开始遍历到N-1，这过程中实际上有许多重复的遍历，例如对于计算 dp[5]，我们会首先计算 dp[1]+dp[4]，之后我们还会重复一次 dp[4]+dp[1]

但是实际上观察以下例子：

dp[5]=dp[4]+dp[1]

dp[6]=dp[4]+dp[1]+dp[1]

dp[7]=dp[4]+dp[3]

我们可以发现，dp[i]总是等于小于 i 的最大的完全平方数 dp[a] 再加上 dp[i-a]，所以我们可以不遍历所有 小于 i 的数，而是仅遍历 小于 i 的完全平方数，就能避免许多重复的计算。

优化之后的代码：

func numSquares(n int) int {
	dp := make([]int, n+1)	
	for i := 1; i <= n; i++ {
		_min := math.MaxInt
		for j := 1; j*j <= i; j++ {
			if j*j == i {
				_min = 1
				break
			} else {
			// dp[j*j]=1
			_min = min(1+dp[i-j*j], _min)
			}
		}
		dp[i] = _min
	}
	return dp[n]
}

我们从1开始完全平方数，对于一个小于 i 的完全平方数 j*j，我们可以从它递推出dp[i]=dp[j*j]+dp[i-j*j]，而 dp[j*j] 总是等于1，所以可以简化为： dp[i]=1+dp[i-j*j]

它的正确性是同样满足的，在计算 i 时，1到i-1 我们都已经计算过了，j*j 是不会超过 i 的，并且如果j*j 等于i，说明 i 本身也是一个完全平方数，可以直接设置 dp[i]=1