题解 | #跳台阶扩展问题#
跳台阶扩展问题
http://www.nowcoder.com/practice/22243d016f6b47f2a6928b4313c85387
题意：
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。
求该青蛙跳上一个n级的台阶(n为正整数)总共有多少种跳法。
方法一：
找规律
思路：
class Solution {
public:
int jumpFloorII(int number) {
return 1<<(number-1);//计算2^(number-1)
}
};
时间复杂度：%2C%E5%B8%B8%E6%95%B0%E7%BA%A7%E5%88%AB%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6%E3%80%82)
空间复杂度：%2C%E5%B8%B8%E6%95%B0%E7%BA%A7%E5%88%AB%E5%AD%98%E5%82%A8%E7%A9%BA%E9%97%B4%E3%80%82)
方法二：
模拟优化
思路：根据方法一的思路：
第 i 项=第 i-1 项 * 2。
累成即可。
class Solution {
public:
int jumpFloorII(int number) {
int res=1;
for(int i=2;i<=number;i++){//累乘2
res*=2;
}
return res;
}
};
时间复杂度：%2C%E4%B8%80%E9%87%8D%E5%BE%AA%E7%8E%AF%E7%9A%84%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6%E3%80%82)
空间复杂度：
查看22道真题和解析