算法学习历程---动态规划（一）

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

用递归的好处就是简单，但是可以看大到，递归有很多重复计算。

比如，当n=4时，
fib(4)=fib(3) + fib(2)
      =fib(2) + fib(1) + fib(1) + fib(0)
      =fib(1) + fib(0) + fib(1) + fib(1) + fib(0)

其中fib(1)就要计算3次，fib(0)要计算2次。

def fib(n):
    memo = [-1] * (n + 1)
    memo[0] = 0
    memo[1] = 1

    for i in range(2, n + 1):
        memo[i] = memo[i - 1] + memo[i - 2]
    return memo[n]

解法二

def fib(n):
    pre = 0
    next = 1
    i = 0
    while i != n:
        next += pre
        pre = next - pre
        i += 1
    return pre