题解:

F(n)=F(n−1)+F(n−2)
由于斐波那契数存在递推关系，因此可以使用动态规划求解。动态规划的状态转移方程即为上述递推关系，边界条件为 F(0)F(0)F(0) 和 F(1)F(1)F(1)。

class Solution {
public:int fib(int n) {int MOD = 1000000007;if (n < 2) {return n;}int p = 0, q = 0, r = 1;for (int i = 2; i <= n; ++i) {p = q; q = r; r = (p + q)%MOD;}return r;}
};

题解:

f(x)=f(x−1)+f(x−2)
表示爬到第 xxx 级台阶的方案数是爬到第 x−1x - 1x−1 级台阶的方案数和爬到第 x−2x - 2x−2 级台阶的方案数的和，即为动态规划的状态转移方程。

class Solution {
public:int climbStairs(int n) {int MOD = 1000000007;int f1 = 0, f2 = 0, f3 = 1;for (int i = 1; i <= n; ++i) {f1 = f2;f2 = f3;f3 = (f1 + f2) % MOD;}return f3;}
};