3动态规划计算斐波那契数列第n项

# 递归是从后向前递归调用，相当于是倒算
# 而动态规划是从前向后计算，每一步计算利用的都是前面已经计算完成的值，不存在调用自身的问题
# 动态规划突破了递归的层数限制
import time


def fibonacci_v3(n, record):
    for i in range(1, n+1):
        if i == 1:
            record[0] = 0
        elif i == 2:
            record[1] = 1
        else:
            if record[i-1] > 0:
                pass
            else:
                record[i-1] = record[i-2] + record[i-3]
    return record[n-1]

if __name__ == '__main__':
    start = time.time()
    print(fibonacci_v3(100000, [0] * 100000))
    end = time.time()
    print(f'用时{end-start}秒')