现在有一栋高楼,但是电梯却出了故障,无奈的你只能走楼梯上楼,根据你的腿长,你一次能走1级或2级楼梯,已知你要走n级楼梯才能走到你的目的楼层,请计算你走到目的楼层的方案数,由于楼很高,所以n的范围为int范围内的正整数。
给定楼梯总数n,请返回方案数。为了防止溢出,请返回结果Mod 1000000007的值。
测试样例:
3
返回:3
import java.util.*; public class GoUpstairs { public int countWays(int n) { long[][] res=new long[][]{{1},{1}}; long[][] base=new long[][]{{1,1},{1,0}}; while(n>0){ if((n&1)>0){ res=multiply(base,res); } base=multiply(base,base); n=n>>1; } return (int) res[1][0]%1000000007; } public long[][] multiply(long[][] a,long[][] b){ int L1=a.length; int L2=a[0].length; int L3=b[0].length; long[][] res=new long[L1][L3]; for(int i=0;i<L1;i++) for(int j=0;j<L3;j++) for(int k=0;k<L2;k++) res[i][j]+=a[i][k]*b[k][j]%1000000007; return res; } }
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次方也是如此。
有了上面的思路,不难写出下面的代码
最后注意:
有不足的地方,希望大家批评指正!