题目

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

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

示例 1：

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

示例 2：

1
2
3
输入：n = 13
输出：2
解释：13 = 4 + 9

提示：

  • 1 <= n <= 104

题解

同样的 DP 题，这里 i 最大的值其实是 sqrt(n) + 1，从这个值进行找就行了。

1）递归公式：如果当前的剩余值，比 i * i 的值要小，就用 i - 1 继续找，否则就 j - (i * i)，然后次数要加 1。

2）初始化两个值：如果 i 为 0（没有可用的数了），j 为 0 时，说明不需要凑，就可以得到 0 了，直接返回 0 即可；否则 j 不为 0 时，就说明凑不出来了。

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
@cache
def dfs(i: int, j: int) -> int:
    # 如果 i 的值为 0，没有任何平方数可用了
    if i == 0:
        # 如果 j 为 0，什么都不用选；不然就是凑不出来了
        return inf if j else 0

    # 如果当前值比 i 方小
    if j < i * i:
        # 就让 i 减小继续找
        return dfs(i - 1, j)
    # 否则用一个 i 方，继续凑，j 需要减值，然后统计次数要增加
    return min(dfs(i - 1, j), dfs(i, j - i * i) + 1)

class Solution:
    def numSquares(self, n: int) -> int:
        # 直接调用函数，isqrt 是计算整数平方根函数
        return dfs(isqrt(n), n)

运行结果

image.png