image.png
典型的動(dòng)態(tài)規(guī)劃問(wèn)題,與斐波那契數(shù)列基本一致稽物。
解法一：自下向上
# -*- coding:utf-8 -*-
class Solution:
def jumpFloor(self, number):
# write code here
f1 = 0
f2 = 1
f = 0
for i in range(1, number+1):
f = f1 + f2
f1 = f2
f2 = f
return f
解法二：自上向下
# -*- coding:utf-8 -*-
class Solution:
def jumpFloor(self, number):
# write code here
self.dp = [0]*(number+1)
return self.jumpDp(number)
def jumpDp(self, n):
if self.dp[n] != 0:
return self.dp[n]
if n == 1:
self.dp[1] = 1
return 1
if n == 2:
self.dp[2] = 2
return 2
self.dp[n] = self.jumpDp(n-2) + self.jumpDp(n-1)
return self.dp[n]
