思路分析
这是一个很经典的题目,但是要注意,这里的跳台阶必须"刚刚好",也就是当只有一个台阶的时候,那么只能选择跳一个台阶的跳法,不能跳两个台阶.
可以正着推,也可以反着推.
还有,跳台阶的问题本质上就是斐波那契的一个变式问题.
如果是39级台阶,那么就是39级到0级, 或者0级到39级.
需要理解,从大到小,在从小到大是一个递归的过程, 直接从小到大是一个递推的过程.
这个题目为了优化,,肯定使用递推的思路.
关于f(0)=1的尝试解释:
这是一个组合问题,那么每次其实都是在选择是走一步还是走两步.
f(1)是一个台阶的时候有几种选法,很显然,只能选一步.
那么f(0)如何解释呢? f(0)就是什么都不选,什么都不选也算是一种组合方式.
递归写法
cpp
class Solution {
public:
int jumpFloor(int number) {
if(number<0)return 0; // 不合法,过了也没有用
if(number==0)return 1;
return jumpFloor(number-1)+jumpFloor(number-2);
}
};
python
# -*- coding:utf-8 -*-
class Solution:
def jumpFloor(self, number):
if number<0: return 0 # 无效跳法
if number==0: return 1 # 有效跳法
return self.jumpFloor(number-1)+self.jumpFloor(number-2)
迭代(递推)写法
cpp
class Solution {
public:
int jumpFloor(int number) {
int a=1,b=1; // 初始值是不一样的
for(int i=0;i<number;i++){
int c = a+b;
a=b,b=c;
}
return a;
}
};
python
# -*- coding:utf-8 -*-
class Solution:
def jumpFloor(self, number):
a,b=1,1
for _ in range(number):
c = a+b
a,b=b,c
return a