小编点评

**子问题的重复计算--递归方法--执行效率低** ```python def fibnacci(n): if n == 1 or n == 2: return 1 else: return fibnacci(n - 1) + fibnacci(n - 2) print(fibnacci(100)) ``` **动态规划（DP）的思想** ```python def fibnacci_no_recurision(n): f = [0, 1, 1] if n > 2: for i in range(n - 2): num = f[-1] + f[-2] f.append(num) return f[n] ``` **归纳总结** 该程序展示了递归方法和动态规划在计算子问题的效率对比。递归方法在计算中重复调用函数，而动态规划通过缓存结果来减少计算时间。 **示例输出** ``` 100 99 ```

正文

博客地址：https://www.cnblogs.com/zylyehuo/

• 

# -*- coding: utf-8 -*-


# 子问题的重复计算--递归方法--执行效率低
def fibnacci(n):
    if n == 1 or n == 2:
        return 1
    else:
        return fibnacci(n - 1) + fibnacci(n - 2)


# print(fibnacci(100))


# 动态规划（DP）的思想 = 递推式 + 重复子问题
def fibnacci_no_recurision(n):
    f = [0, 1, 1]
    if n > 2:
        for i in range(n - 2):
            num = f[-1] + f[-2]
            f.append(num)
    return f[n]


print(fibnacci_no_recurision(100))