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 ```