1117. Fibonacci Number (Bottom-Up DP)

The Fibonacci sequence is defined by F(0)=0, F(1)=1, and F(n)=F(n-1)+F(n-2) for n>=2. Given n, return F(n) using bottom-up dynamic programming. The input is JSON {n}.

Input: JSON {n}.

Output: Integer — the nth Fibonacci number.

Examples

Input: {"n":10}
Output: 55
Explanation: F(10) = 55.

Input: {"n":0}
Output: 0
Explanation: Base case.

Input: {"n":1}
Output: 1
Explanation: Base case.

Constraints

• 0<=n<=90

Asked by