class Solution(object):
def Fibonacci(self, n):
"""
:type n: int
:rtype: int
"""
# print(n)
dp=[0 for x in range(n+1)]
if n==0:
return dp[0]
else:
if n==1:
dp[1]=1
return dp[1]
else:
dp[1]=1
for x in range(2,n+1):
dp[x]=dp[x-1]+dp[x-2]
# print(dp[n])
return dp[n]