Bottom-Up算法实现斐波那契数列报KeyError:0，求问题排查

问题描述 #

我正在学习动态规划，尝试使用Bottom-Up算法实现斐波那契数列，希望将斐波那契序列的每个元素存入名为fib的字典中，但运行时出现了KeyError:0的异常。

异常信息 #

C:\Users\Wandres\venv\insertionsort\Scripts\python.exe C:/Users/Wandres/PycharmProjects/insertionsort/fibobottomup.py
Traceback (most recent call last):
  File "C:\Users\Wandres\PycharmProjects\insertionsort\fibobottomup.py", line 13, in <module>
    print(fibbottonup(5))
  File "C:\Users\Wandres\PycharmProjects\insertionsort\fibobottomup.py", line 8, in fibbottonup
    f=fib[k-1]+fib[k-2]
KeyError: 0

原代码 #

def fibbottonup (n):  
    fib = {}     
    for  k in range (1, n + 1):    
        if k<2:       
           f=1            
           fib[k]=f        
        else:             
           f=fib[k-1] + fib[k-2]            
           fib[k]=f     
    return fib[n] 

错误原因 #

当循环执行到k=2时，代码尝试访问fib[k-2]即fib[0]，但字典fib中只初始化了k=1的键值对，不存在0这个键，因此触发KeyError。

你的逻辑默认k<2时斐波那契值为1（对应F(1)=1、F(2)=1的定义），但循环从k=1开始，当k=2进入else分支时，会去读取未定义的fib[0]。

修正方案 #

方案一：遵循标准斐波那契定义（F(0)=0, F(1)=1） #

提前初始化基础键值对，避免访问不存在的键：

def fibbottonup(n):  
    fib = {}     
    # 初始化基础情况
    fib[0] = 0
    fib[1] = 1
    # 从k=2开始计算后续值
    for k in range(2, n + 1):    
        f = fib[k-1] + fib[k-2]            
        fib[k] = f     
    return fib[n] 

方案二：保持原数值逻辑（F(1)=1, F(2)=1） #

调整判断条件，让k=2时直接赋值，无需访问fib[0]：

def fibbottonup(n):  
    fib = {}     
    for k in range(1, n + 1):    
        if k <= 2:  # 把判断条件改为k<=2，覆盖k=1和k=2的情况
           f = 1            
           fib[k] = f        
        else:             
           f = fib[k-1] + fib[k-2]            
           fib[k] = f     
    return fib[n] 

内容的提问来源于stack exchange，提问作者weymar andres