题解 | #跳台阶#
跳台阶
http://www.nowcoder.com/practice/8c82a5b80378478f9484d87d1c5f12a4
题意：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
方法一：
递推
思路：dp[i]表示到达第 i 级台阶的方案数。因为一次可以跳上1级台阶，也可以跳上2级，所以第 i 级台阶可以是从i-1或i-2级台阶过来的。因此第 i 级台阶的方案数等于从第i-1和第i-2级台阶的方案数之和。（即）
class Solution {
public:
int jumpFloor(int number) {
vector<int> dp(number+1,0);
dp[1]=1;//初始化
dp[2]=2;
for(int i=3;i<=number;i++){//遍历
dp[i]=dp[i-1]+dp[i-2];
}
return dp[number];
}
};
时间复杂度：%2Cn%E6%98%AF%E5%8F%B0%E9%98%B6%E6%95%B0%E3%80%82)
空间复杂度：
方法二：
递推+空间优化
思路：沿用方法一的思路，做空间优化。设x=1,y=2分别是台阶数为1和2的情况（即初始化）。
class Solution {
public:
int jumpFloor(int number) {
if(number<=1)
return number;
int x=1,y=2,t;//初始化
for(int i=3;i<=number;i++){//遍历
t=y;
y=x+y;
x=t;//x赋值为原先的y
}
return y;
}
};
时间复杂度：
空间复杂度：%2C%E4%B8%8D%E9%9C%80%E9%A2%9D%E5%A4%96%E5%AD%98%E5%82%A8)
投递中车集团等公司7个岗位 >