求正整数n减至1的最小步数：大数值输入时程序崩溃问题排查

问题原因 #

你的代码处理大数值时崩溃，核心原因是递归深度超出Python默认栈限制。Python默认递归深度约为1000，当n较大（比如5685）时，递归调用链会被拉得极长，直接触发栈溢出错误，导致进程终止或内核崩溃。

你看到字典dic为空，是因为栈溢出发生在递归调用过程中，程序还没来得及将计算结果存入字典就崩溃了，并非字典缓存逻辑本身的问题。小数值n的递归层数少，不会触发栈溢出，所以能正常运行并填充字典。

修复方案 #

改用迭代式动态规划替代递归，从1开始逐步计算到目标n，完全避免递归栈问题，同时时间复杂度和空间复杂度都能满足1e6的约束。

优化后的代码 #

def countMinStepsToOne(n):
    if n == 1:
        return 0
    # dp数组存储每个数到1的最小步数
    dp = [0] * (n + 1)
    dp[1] = 0
    for i in range(2, n + 1):
        # 初始化为减1操作的步数
        dp[i] = dp[i-1] + 1
        # 如果能被2整除，取更小值
        if i % 2 == 0:
            dp[i] = min(dp[i], dp[i//2] + 1)
        # 如果能被3整除，取更小值
        if i % 3 == 0:
            dp[i] = min(dp[i], dp[i//3] + 1)
    return dp[n]

n = int(input())
print(countMinStepsToOne(n))

代码说明 #

1. 用dp数组记录每个数到1的最小步数，dp[i]表示将i减到1的最小操作数。
2. 从2开始遍历到n，依次计算每个数的最小步数：
   • 先默认取dp[i-1]+1（减1操作）的步数；
   • 如果i能被2整除，对比dp[i//2]+1（除以2操作）的步数，取较小值；
   • 如果i能被3整除，对比dp[i//3]+1（除以3操作）的步数，取较小值。
3. 这种迭代方式不会产生递归栈，能轻松处理n=1e6的情况，时间复杂度O(n)，空间复杂度O(n)（对于1e6来说，数组占用内存约4MB，完全在可接受范围内）。

原代码的其他潜在问题 #

原递归代码除了栈溢出问题，还有一个细节bug：当n是整数时，n/3和n/2会得到浮点数（比如3/3=1.0），这会导致字典的键是浮点数，而后续调用n-1得到的是整数，出现键类型不一致的情况（比如1和1.0是不同的键），虽然小数值时可能碰巧能运行，但这是需要避免的问题。优化后的代码用整数除法//彻底解决了这个问题。

内容的提问来源于stack exchange，提问作者Suman Saurabh