青蛙跳台阶

1.题目描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

2.思路

动态规划，问题转化为斐波那契数列问题，f(0)=0,f(1)=1,f(2)=2......f(n)=f(n−1)+f(n−2),n>=3f(0) = 0,f(1)=1,f(2)=2......f(n) = f(n-1) + f(n-2),n>=3f(0)=0,f(1)=1,f(2)=2......f(n)=f(n−1)+f(n−2),n>=3。

3.代码

class Solution {public:int jumpFloor(int number) {vector<int> res;res.resize(number+1);res[0] = 0;res[1] = 1;res[2] = 2;if(number < 3){return res[number];}for(int i = 3;i <= number;++i){res[i] = res[i-1] + res[i-2];}return res[number];}};

4.复杂度分析

时间复杂度：O(n)

空间复杂度：O(n)

5.方法2

由于dp[i]=dp[i−1]+dp[i−2]，考虑到 dp[i] 只与 dp[i - 1] 和 dp[i - 2] 有关因此可以用两个变量pre1，pre2代替dp[i-1]，dp[i-2]。

6.代码

class Solution {public:int climbStairs(int n) {if(n <= 2){return n;}int pre2 = 1,pre1 = 2;//1阶楼梯时有1种方法，2阶楼梯有两种方法for(int i = 3;i <= n;++i){int count = pre1 + pre2;//第i个楼梯可以由前i-1个楼梯和i-2个楼梯爬一步得到pre2 = pre1;pre1 = count;}return pre1;}};

7.复杂度分析

时间复杂度：O(n)

空间复杂度：O(1)