求组成目标数的最少平方数的记忆化代码报KeyError求修正

错误原因 #

• 缓存存在性判断逻辑错误：原代码在判断时直接调用了cache[nc]，此时如果nc不存在于缓存字典的键中，就会直接触发KeyError
• 原本的判断逻辑应该是校验nc是否在缓存的键中，而非校验cache[nc]是否在缓存中

修正后代码 #

import sys
# 处理大输入时可以放开下面的递归深度限制
# sys.setrecursionlimit(10**5)
import math
cache = {}

def m(n):
    if n == 0:
        return 0
    # 新增当前n的缓存校验，避免重复计算
    if n in cache:
        return cache[n]
    ans = sys.maxsize
    root = int(math.sqrt(n))
    for i in range(1, root + 1):
        nc = n - (i ** 2)
        # 修正判断逻辑，只校验nc是否为缓存的键
        if nc not in cache:
            sa = m(nc)
            cache[nc] = sa
        curr = 1 + cache[nc]
        ans = min(ans, curr)
    # 把当前n的计算结果存入缓存，提升后续计算效率
    cache[n] = ans
    return ans

print(m(int(input())))

内容的提问来源于stack exchange，提问作者Divyanshu Singh