1. 题目描述
斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给你 n ，请计算 F(n) 。
来源：力扣（LeetCode）
链接：https://leetcode-/problems/fibonacci-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 解法
思路：动态规划。
动规五部曲：
确定dp数组（dp table）以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举例推导dp数组
上面的五个部分的详细信息都嵌在代码中。
int fib(int n) {// 1. dp[i] : 第 i 个斐波那契数// 2. 递推公式： dp[i] = dp[i - 1] + dp[i - 2]// 3. dp数组初始化： dp[0] = 0, dp[1] = 1;// 4. 确定遍历顺序： 只知道前两个状态，要递推后面状态，那么顺序肯定是从前到后；// 5. 举例dp，0,1，1,2,3,5,8,13,21,34,55；int dp[n + 1];if(n == 0 || n == 1) return n;dp[0] = 0; dp[1] = 1;for(int i = 2; i <= n; ++i){dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];}
我们可以发现，当前状态仅与前两个状态相关，所以我们不需要记录前面所有的数据，只保留前两个状态即可。
int fib(int n) {int dp[n + 1];if(n == 0 || n == 1) return n;int a = 0; int b = 1;for(int i = 2; i <= n; ++i){int sum = a + b;a = b;b = sum;}return b;}
