剑指Offer：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法
暴力法
思路：
按照函数调用的递归树,记录符合条件的跳跃操作：
python代码：
class Solution:
def __init__(self):
self.solutions = 0
pass
def jump(self, start, end):
if start > end:
return 0
elif start == end:
return 1
return self.jump(start + 1, end) + self.jump(start + 2, end)
def jumpFloor(self, number):
if number == 0:
return 0
self.solutions = self.jump(0, number)
return self.solutions
if __name__ == '__main__':
s = Solution()
for i in range(0, 20):
s.solutions = 0
print(s.jumpFloor(i), end=',')
时间复杂度：
python代码：
class Solution:
def __init__(self):
self.solutions = 0
self.mem = []
pass
def jump(self, start, end):
if start > end:
return 0
elif start == end:
return 1
if self.mem[start] > 0:
return self.mem[start]
self.mem[start] = self.jump(start + 1, end) + self.jump(start + 2, end)
return self.mem[start]
def jumpFloor(self, number):
self.mem = [0 for _ in range(number)]
if number == 0:
return 0
self.solutions = self.jump(0, number)
return self.solutions
if __name__ == '__main__':
s = Solution()
for i in range(0, 20):
s.solutions = 0
print(s.jumpFloor(i), end=',')
时间复杂度：
python代码：
class Solution:
def jumpFloor(self, number):
res = [0, 1, 2]
while len(res) <= number:
res.append(res[-1]+res[-2])
return res[number]
if __name__ == '__main__':
s = Solution()
for i in range(0, 20):
print(s.jumpFloor(i), end=',')
由于用res存储了对0～number不同长度的方案数目，所以
时间复杂度：
空间复杂度：，如果只记录长度为number时的方案数，空间复杂度可降低为
__COMA__
原创文章 4获赞 0访问量 88
关注
私信
展开阅读全文
作者：__COMA__
