leetcode

class :
    def fib(self, N: int) -> int:
        if (N == 0):
            return 0
        elif (N == 1):
            return 1
        else:
            return self.fib(N-1) + self.fib(N-2)
# 方法二
class :
    def fib(self, N: int) -> int:
        if (N == 0):
            return 0
        elif (N == 1):
            return 1
        else:
            ans = [0] * (N + 1)
            ans[0], ans[1] = 0, 1 # 初始状态
            for i in range(2, N+1):
                ans[i] = ans[i-1] + ans[i-2] # 状态转移方程
            return ans[N]