class Solution:
    def numSquares(self, n: int) -> int:
        # 完全背包
        s = math.sqrt(n)
        if s // 1 == s:
            return 1
        s = floor(s)
        @cache
        def dfs(i, c):
            if i == 0: # 为什么是==
                return 0 if c == 0 else inf
            # 不选
            if i ** 2 > c:
                return dfs(i-1, c)
            return min(dfs(i,c-(i ** 2))+1, dfs(i-1,c))
        return int(dfs(s, n))


"""
“多个测试数据之间可以共享” 指的是——在一次提交代码的执行过程中，OJ （在线评测系统）会依次把同一份代码拿去跑很多组输入 n。
如果某些中间结果（这里是 dfs(i, j) 的结果）已经在前一道测试里算过了，就可以直接拿来复用，后面的测试不用再重新递归计算，从而 节省时间。
"""
# 写在外面，多个测试数据之间可以共享，减少计算量
@cache  # 缓存装饰器，避免重复计算 dfs 的结果（记忆化）
def dfs(i: int, j: int) -> int:
    if i == 0:
        return inf if j else 0
    if j < i * i:
        return dfs(i - 1, j)  # 只能不选
    return min(dfs(i - 1, j), dfs(i, j - i * i) + 1)  # 不选 vs 选

class Solution:
    def numSquares(self, n: int) -> int:
        return dfs(isqrt(n), n)

from pprint import pprint
class Solution:
    def numSquares(self, n: int) -> int:
        s = isqrt(n)
        f = [[0] * (n+1) for _ in range(s+1)]
        f[0] = [0] + [inf] * n
        for i in range(1, len(f)):
            for j in range(len(f[0])):
                if j < i * i:
                    f[i][j] = f[i-1][j]
                else:
                    f[i][j] = min(f[i-1][j], f[i][j- i*i]+1)
        pprint(f)
        return f[s][n]

from pprint import pprint
class Solution:
    def numSquares(self, n: int) -> int:
        s = isqrt(n)
        f = [[0] * (n+1) for _ in range(2)]
        f[0] = [0] + [inf] * n
        for i in range(1, s+1):
            for j in range(n+1):
                if j < i * i:
                    f[i%2][j] = f[(i-1)%2][j]
                else:
                    f[i%2][j] = min(f[(i-1)%2][j], f[i%2][j- i*i]+1)
        pprint(f)
        return f[s%2][n]