通过这个简单的题目来入门动态规划和递归。

不是所有的递归都需要动态规划，只有大问题分叉为子问题，并且子问题需要重复计算，重叠计算才需要动态规划。

509. 斐波那契数

https://leetcode-cn.com/problems/fibonacci-number/

斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给你 n ，请计算 F(n) 。

代码：

# 特点要重复计算其值,动态规划的经典列子
# 运用递归

def fib(n: int) -> int:
    if n == 0 or n == 1:
        return n
    return fib(n - 1) + fib(n - 2)


def fib_mem(n: int, mem: list) -> int:
    # 不需要计算
    if n == 0 or n == 1:
        return n
    # 存在数值，不需要计算
    if mem[n]:
        return mem[n]
    # 需要计算
    mem[n] = fib_mem(n - 1, mem) + fib_mem(n - 2, mem)
    return mem[n]


def fib_iter(n):
    ans = 0
    if n == 0 or n == 1:
        return n
    pre, next_fib = 0, 1
    for i in range(1, n):
        ans = pre + next_fib  # n
        pre = next_fib  # n-1
        next_fib = ans  # n-2
    return ans