题解 | #跳台阶#
跳台阶
http://www.nowcoder.com/practice/8c82a5b80378478f9484d87d1c5f12a4
题意：
一只青蛙一次可以跳上1级台阶，也可以跳上2级。
求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
方法一：
动态规划
思路：当前项等于前两项之和。状态转移方程：
dp[i]=dp[i-1]+dp[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];
}
};
时间复杂度：%EF%BC%8C%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)
空间复杂度：%EF%BC%8C%E4%B8%80%E7%BB%B4%E5%AD%98%E5%82%A8%E7%A9%BA%E9%97%B4%E3%80%82)
方法二：
空间优化
思路：利用两个变量实现当前项等于前两项之和。并不断更新 x 和 y 的值。
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;
}
return y;
}
};
时间复杂度：空间复杂度：%EF%BC%8C%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)
投递微众银行等公司6个岗位