劍指offer 斐波那契系列
T9-斐波那契用迭代
跳臺階
動規 py2
# -*- coding:utf-8 -*-
class Solution:
def jumpFloor(self, number):
# write code here
if number<0:
return -1
if number <=2:
return number
a,b=1,2
res = 0
for i in range(3,number+1):
res = a+b
a,b = b,res
return res
變態跳臺階
wo的初始迭代方法
# -*- coding:utf-8 -*-
class Solution:
def jumpFloorII(self, number):
# write code here
if number<0:
return -1
res = [0,1]
for i in range(2,number+1):
res.append(sum(res)+1)
return res[number]
數學--移位 py2
調到第n級臺階,前面的(n-1)級有跳與不跳兩種選擇嗎,故答案為2^(n-1),并且用移位運算代替乘法運算來優化。
# -*- coding:utf-8 -*-
class Solution:
def jumpFloorII(self, number):
# write code here
if number<=0:
return -1
res = 1
return res<<(number-1)
矩形覆蓋
## 動規 Py2
```
# -*- coding:utf-8 -*-
class Solution:
def rectCover(self, number):
# write code here
if number<0:
return -1
if number<=2:
return number
a,b=1,2
res=0
for i in range(3,number+1):
res = a+b
a ,b = b,res
return res
```
浙公網安備 33010602011771號