动态规划

其中 n == 0 的时候返回 0；n == 1 的时候返回 1，所以我们就可以缩写成 if n < 2: return n。

# -*- coding:utf-8 -*-
class Solution:
    def Fibonacci(self, n):
        if n < 2: return n
        dp = [0, 1] + [0] * (n - 1)
        for i in range(2, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]
        return dp[n]