青蛙跳台阶
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)