509. 斐波那契數

斐波那契數?（通常用?F(n)?表示）形成的序列稱為?斐波那契數列?。該數列由?0?和?1?開始，后面的每一項數字都是前面兩項數字的和。也就是：

F(0) = 0，F(1)?= 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

給定?n?，請計算?F(n)?。

示例 1：

輸入：n = 2
輸出：1
解釋：F(2) = F(1) + F(0) = 1 + 0 = 1

示例 2：

輸入：n = 3
輸出：2
解釋：F(3) = F(2) + F(1) = 1 + 1 = 2

示例 3：

輸入：n = 4
輸出：3
解釋：F(4) = F(3) + F(2) = 2 + 1 = 3

提示：

• 0 <= n <= 30

class Solution {public int fib(int n) {if(n<2)return n;int[] dp = new int[n+1];dp[0]=0;dp[1]=1;for(int i = 2;i < n+1;i++){dp[i] = dp[i-1]+dp[i-2];}return dp[n];}
}