BM63. [跳台阶]
https://www.nowcoder.com/exam/oj?tab=%E7%AE%97%E6%B3%95%E7%AF%87&topicId=295
BM63. 跳台阶
思路：
题目分析：
一只青蛙一次可以跳1阶或2阶，直到跳到第n阶，也可以看成这只青蛙从n阶往下跳，到0阶，按照原路返回的话，两种方法事实上可以的跳法是一样的——即怎么来的，怎么回去！
当青蛙在第n阶往下跳，它可以选择跳1阶到n-1，也可以选择跳2阶到n-2，即它后续的跳法变成了f(n-1)+f(n-2),这就变成了斐波那契数列。因此可以按照斐波那契数列的做法来做：即输入n，输出第n个斐波那契数列的值。
方法一：递归法
根据斐波那契数列的函数，书写递归，需要注意这里第2阶为2，而不是之前斐波那契数列中的1：
class Solution {
public:
int jumpFloor(int number) {
if(number <= 1)//不同于斐波那契数列那道题，这里第0项为1，第1项为1，因为实际问题实际考虑
return 1;
else
return jumpFloor(number - 1) + jumpFloor(number - 2);
}
};复杂度分析：
- 时间复杂度：O(2^n)，由图可知，每个递归会调用两个递归，因此呈现2的指数增长
- 空间复杂度：O(n), 栈空间最大值
方法二：递归改进
递归虽然简单，但是从上图可以看出，重复计算了很大一部分，可以利用数组记录每个F(n)，需要的时候直接调用数组里面的值即可。
class Solution {
public:
int dp[50] = {0};//设置全局变量，因为实际问题中没有0，则可用0作初始标识值
int F(int n){
if(n <= 1)
return 1;
if(dp[n] != 0) //若是dp中有值则不需要重新递归加一次
return dp[n];
return dp[n] = F(n - 1) + F(n - 2);//若是dp中没有值则需要重新递归加一次
}
int jumpFloor(int number) {
return F(number);
}
};复杂度分析：
- 时间复杂度：每个数字只算了一次，故为O(n)
- 空间复杂度：O(n)，栈空间最大深度
方法三：动态规划
具体做法：创建一个n+1大小的动态数组temp，初始化第0位为1，第1位为1，然后根据公式相加即可得到后面的，数组最后的下标n即为所求。
class Solution {
public:
int jumpFloor(int n) {
if (n <= 1) //从0开始，第0项是1，第一项是1
return n;
int* temp = new int[n+1];
temp[0] = 1;
temp[1] = 1;
for (int i = 2; i <= n; i++)
{
temp[i] = temp[i-1] + temp[i-2];
}
return temp[n];
}
};复杂度分析：
- 时间复杂度：O(n)
- 空间复杂度：O(n)，建立了一个数组
