Python斐波那契DP代码运行报SyntaxError，求排查解决

问题场景 #

执行命令python fibonacci.py 10 dp all，尝试通过DP（动态规划）方法生成前10项斐波那契数列时，触发语法错误，报错指向def fib_dp(n: int) -> int:行，错误信息如下：

File "fibonacci.py", line 30
    def fib_dp(n: int) -> int:
                ^
SyntaxError: invalid syntax

错误原因分析 #

1. Python版本不支持类型提示：函数参数和返回值的类型标注（如n: int、-> int）是Python 3.5及以上版本引入的特性，若使用Python 2或低于3.5的版本，会直接触发语法错误。
2. 变量引用顺序错误：代码中先定义fib_table = [INVALID] * MAX_FIB，但INVALID的定义在这之后，运行时会出现NameError: name 'INVALID' is not defined错误。
3. 泛型类型提示兼容问题：get_entire_row函数返回值标注list[int]是Python 3.9+的写法，低于该版本需要使用typing.List模块。

修复步骤 #

1. 处理版本兼容问题 #

如果无法升级Python版本，直接移除所有函数的类型提示。以fib_dp为例，修改后：

@lru_cache(maxsize=None)
def fib_dp(n):
    """
    用递归结合内置缓存实现斐波那契数列求解
    参数:
        n: 第n项的索引
    返回:
        第n项斐波那契数值
    """
    if n < 0:
        return INVALID
    if fib_table[n] != INVALID:
        return fib_table[n]
    fib_table[n] = fib_dp(n - 1) + fib_dp(n - 2)
    return fib_table[n]

同时对fib_iter、fib_rec、get_entire_row、get_nth和main函数执行相同操作，移除所有参数和返回值的类型标注。

2. 调整变量定义顺序 #

将INVALID的定义移到fib_table之前，避免未定义引用：

# 备忘录表的无效值标记
INVALID = -1
# 斐波那契备忘录表
fib_table = [INVALID] * MAX_FIB

3. 修复泛型类型提示（Python 3.8及以下版本适用） #

导入typing.List模块，替换list[int]为List[int]：

from typing import List
# ...
def get_entire_row(n, type, print_it) -> List[int]:
    entire_row = []
    # 函数原有逻辑不变

修复后的完整代码 #

from enum import Enum
from functools import lru_cache
import click
import sys
from typing import List  # 适配Python 3.8及以下版本

STACK_LIMIT = 1000
MAX_FIB = 500
sys.setrecursionlimit(100000)

class FibonacciType(Enum):
    DP = 2
    RECURSIVE = 1
    ITERATIVE = 0

# 备忘录表的无效值标记
INVALID = -1
# 斐波那契备忘录表
fib_table = [INVALID] * MAX_FIB

@lru_cache(maxsize=None)
def fib_dp(n):
    """
    用递归结合内置缓存实现斐波那契数列求解
    参数:
        n: 第n项的索引
    返回:
        第n项斐波那契数值
    """
    if n < 0:
        return INVALID
    if fib_table[n] != INVALID:
        return fib_table[n]
    fib_table[n] = fib_dp(n - 1) + fib_dp(n - 2)
    return fib_table[n]

def fib_iter(n):
    if n in {0, 1}:
        return n

    x, y, curr = 0, 1, 0
    for i in range(2, n + 1):
        curr = x + y
        x = y
        y = curr
    return curr

def fib_rec(n):
    if n < 0:
        return 0
    if n == 0 or n == 1:
        return n
    return fib_rec(n - 1) + fib_rec(n - 2)

def get_entire_row(n, type, print_it) -> List[int]:
    entire_row = []

    if type == 0:
        for i in range(n):
            entire_row.append(fib_iter(i))
    elif type == 1:
        for i in range(n):
            entire_row.append(fib_rec(i))
    elif type == 2:
        for i in range(MAX_FIB):
            fib_table[i] = INVALID

        fib_table[0] = 0
        fib_table[1] = 1

        for i in range(n):
            entire_row.append(fib_dp(i))

    if print_it:
        print(entire_row)
    return entire_row

def get_nth(n, type):
    if type == 0:
        print(fib_iter(n))
    elif type == 1:
        print(fib_rec(n))
    elif type == 2:
        for i in range(MAX_FIB):
            fib_table[i] = INVALID

        fib_table[0] = 0
        fib_table[1] = 1

        print(fib_dp(n))

@click.command()
@click.argument("n", type=click.IntRange(min=0, max=50000, clamp=True))
@click.option("--algo", type=click.Choice(['recursive', 'dp', 'iterative'], case_sensitive=False), default='iterative')
@click.option("--print-type", type=click.Choice(['all', 'none', 'Nth'], case_sensitive=False), default='none')
def main(n, algo, print_type):
    """
    生成并打印斐波那契数列的指定项或完整序列。

    参数:
        n: 要生成的数列长度或指定项的索引
        algo: 使用的算法类型
        print_type: 打印模式（全部、仅第n项、不打印）
    """
    print_it = print_type == 'all'
    t = FibonacciType.ITERATIVE
    if algo == 'recursive':
        t = FibonacciType.RECURSIVE
    elif algo == 'dp':
        t = FibonacciType.DP
    row = get_entire_row(n, t.value, print_it)

    if print_type == 'all':
        print(row)
    elif print_type == 'Nth':
        get_nth(n, t.value)

if __name__ == '__main__':
    main()

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