ClimbingStairs

Leetcode

---

典型的斐波那契数列问题。但是用常规的思维解题无法做到高效。
高效算法思路如下：基本思路公式$F(n+1)=F(n)+F(n-1)$用矩阵表示：

$$\begin{bmatrix} F(n+1)\\ F(n)\\ \end{bmatrix} = \begin{bmatrix} F(n)+F(n-1)\\ F(n)\\ \end{bmatrix} =A* \begin{bmatrix} F(n)\\ F(n-1)\\ \end{bmatrix}$$
由中间矩阵第一行有两项得，矩阵$A$必然是二阶矩阵。得：
$$\begin{bmatrix} F(n+1)\\ F(n)\\ \end{bmatrix} = \begin{bmatrix} F(n)+F(n-1)\\ F(n)\\ \end{bmatrix} = \begin{bmatrix} a&b\\ c&d\\ \end{bmatrix} * \begin{bmatrix} F(n)\\ F(n-1)\\ \end{bmatrix}$$
解得a=1,b=1,c=1,d=0;则矩阵$A$为
$A= \begin{bmatrix} 1&1\\ 1&0\\ \end{bmatrix}$
,斐波那契初始值$F(1)=1,F(2)=2$
那么得
$$\begin{bmatrix} F(n+1)\\ F(n)\\ \end{bmatrix} = \begin{bmatrix} 1&1\\ 1&0\\ \end{bmatrix}^{n-2} * \begin{bmatrix} F(2)\\ F(1)\\ \end{bmatrix}$$
可得$F(n+1)$,然后是快速乘法和快速幂对常数的计算，时间复杂度为$O(logn)$

'''python3
# File: climbStairs.py
# Author: 0HP
# Date: 20200203
# Purpose: solve the problem in website: https://leetcode.com/problems/climbing-stairs/
'''
class Solution:
    def Qmul(self,a: int,b: int):
        result=0
        while b:
            if b&1: #b's last bit is 1
                result+=a
            b=b>>1#b=b/2
            a=a<<1#a=a*2
        return result
    def MatrixMul(self,a: [[]],b: [[]]):
        #row of b = col of a
        Arow,Brow,Bcol=2,2,2
        c=[[0,0],[0,0]]
        for i in range(2):
            for j in range(2):
                c[i][j]=self.Qmul(a[i][0],b[0][j])+self.Qmul(a[i][1],b[1][j])
        return c
    def MatrixPow(self,a: [[]],b: int):
        result=[[1,0],[0,1]]
        while b:
            if b&1:
                result=self.MatrixMul(result,a)
            b=b>>1
            a=self.MatrixMul(a,a)
        return result
    def climbStairs(self, n: int) -> int:
        if n==1 or n==2:
            return n
        A=[[1,1],[1,0]]
        F=[[2],[1]]
        A=self.MatrixPow(A,n-2)
        result=self.Qmul(A[0][0],F[0][0])+self.Qmul(A[0][1],F[1][0])
        return result
t=Solution()
print(t.climbStairs(6))