现在有一栋高楼,但是电梯却出了故障,无奈的你只能走楼梯上楼,根据你的腿长,你一次能走1级或2级楼梯,已知你要走n级楼梯才能走到你的目的楼层,请计算你走到目的楼层的方案数,由于楼很高,所以n的范围为int范围内的正整数。
给定楼梯总数n,请返回方案数。为了防止溢出,请返回结果Mod 1000000007的值。
测试样例:
3
返回:3
# -*- coding:utf-8 -*- #思路大致是:由递推公式得到简化后的矩阵运算式: #( f(n),f(n-1) ) = ( f(2), f(1) ) * matrix(n-2) #其中,int[][] matirx = { {1,1},{1,0}}。 #时间复杂度的降低,在于降低求矩阵的n次方的时间复杂度。 def MatrixMul(a, b):#矩阵相乘 r = [[0, 0], [0, 0]] r[0][0] = (a[0][0]*b[0][0] + a[0][1]*b[1][0]) % 1000000007 r[0][1] = (a[0][0]*b[0][1] + a[0][1]*b[1][1]) % 1000000007 r[1][0] = (a[1][0]*b[0][0] + a[1][1]*b[1][0]) % 1000000007 r[1][1] = (a[1][0]*b[0][1] + a[1][1]*b[1][1]) % 1000000007 return r def QuickMatrixPower(A, n):#快速求矩阵的N次方 if n == 1: return A Temp = QuickMatrixPower(A, n / 2) if n % 2 == 1: return MatrixMul(MatrixMul(Temp, Temp), A) return MatrixMul(Temp, Temp) class GoUpstairs: def countWays(self, n): if n <= 3: return [1, 2, 3][n - 1] else: return MatrixMul(QuickMatrixPower([[1, 1],[1, 0]], n - 1),[[1, 2],[1, 1]])[0][0] % 100000000
# -*- coding:utf-8 -*- def MatrixMul(a, b): r = [[0, 0], [0, 0]] r[0][0] = (a[0][0]*b[0][0] + a[0][1]*b[1][0]) % 1000000007 r[0][1] = (a[0][0]*b[0][1] + a[0][1]*b[1][1]) % 1000000007 r[1][0] = (a[1][0]*b[0][0] + a[1][1]*b[1][0]) % 1000000007 r[1][1] = (a[1][0]*b[0][1] + a[1][1]*b[1][1]) % 1000000007 return r def QuickMatrixPower(A, n): if n == 1: return A Temp = QuickMatrixPower(A, n / 2) if n % 2 == 1: return MatrixMul(MatrixMul(Temp, Temp), A) return MatrixMul(Temp, Temp) class GoUpstairs: def countWays(self, n): if n <= 3: return [1, 2, 3][n - 1] else: return MatrixMul(QuickMatrixPower([[1, 1],[1, 0]], n - 1),[[1, 2],[1, 1]])[0][0] % 1000000007
http://www.nowcoder.com/discuss/1820
思路大致是:由递推公式得到简化后的矩阵运算式:
( f(n),f(n-1) ) = ( f(2), f(1) ) * matrix(n-2)
其中,int[][] matirx = { {1,1},{1,0}}。
时间复杂度的降低,在于降低求矩阵的n次方的时间复杂度。
求一个整数m的n次方的时候,我们可以先求出n的二进制表达,具体求解的时候就变成了,二进制上为1的各位的m的相应次方的乘积。
比如,程云老师的例子中,提到:
假设⼀个整数是10,如何最快的求解10的75次⽅。
1, 75的⼆进制形式为1001011。
2, 10的75次⽅=(10^64) * (10^8) * (10^2) * (10^1)。
由此,矩阵的n次方也是如此。
有了上面的思路,不难写出下面的代码
最后注意:
有不足的地方,希望大家批评指正!