题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是定义那些正整数自平方所得的叫完全平方数，现在给一个数字 n，问这个数字 n 被划分为完全平方数的个数最少是多少。

思路分享

代码解答（强烈建议自行解答后再看）

  • 参考题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
@cache
def dfs(i:int, amount:int)->int:
    # print(i, amount)
    if i == 0:
        return 0 if amount == 0 else inf
    if i**2 > amount:
        return dfs(i-1, amount)
    else:
        return min(dfs(i, amount-i**2)+1, dfs(i-1, amount))
class Solution:
    def numSquares(self, n: int) -> int:
        # 空间优化
        m = isqrt(n)
        f = [inf]*(n+1)
        f[0] = 0
        for i in range(1, m+1):
            for j in range(i**2, n+1):
                f[j] = min(f[j-i**2]+1, f[j])
        return f[n]

        # 递推
        m = isqrt(n)
        f = [[inf]*(n+1) for _ in range(m+1)]
        f[0][0] = 0
        

        # 记忆化搜索，由于函数写类的函数内，会有 self i amount 绑定缓存，内存占得多，放全局就好些
        # 在 i*2 下想法凑 amount
        ans = dfs(isqrt(n), n)
        return ans if ans != inf else 0