现在有一栋高楼,但是电梯却出了故障,无奈的你只能走楼梯上楼,根据你的腿长,你一次能走1级或2级楼梯,已知你要走n级楼梯才能走到你的目的楼层,请计算你走到目的楼层的方案数,由于楼很高,所以n的范围为int范围内的正整数。
给定楼梯总数n,请返回方案数。为了防止溢出,请返回结果Mod 1000000007的值。
3
返回:3
public class GoUpstairs { public static final int Mod = 1000000007; public int countWays(int n) { if (n < 1) { return 0; } if (n == 1 || n == 2) { return n; } long[][] matrix = { { 1, 1 }, { 1, 0 } }; long[][] res = matrixPower(matrix, n - 2); return (int) (2 * res[0][0] % Mod + res[1][0] % Mod) % Mod; } // 计算矩阵的n次方 public long[][] matrixPower(long[][] m, int n) { long[][] res = new long[m.length][m[0].length]; // 先把res设为单位矩阵,相当于整数中的1 for (int i = 0; i < res.length; i++) { res[i][i] = 1; } long[][] tmp = m; for (; n != 0; n >>= 1) { // 对n的每个二进制位进行判断 if ((n & 1) != 0) { // 最后一位为1 res = matrixMul(res, tmp); } tmp = matrixMul(tmp, tmp); } return res; } // 两个矩阵相乘 public long[][] matrixMul(long[][] m1, long[][] m2) { long[][] res = new long[m1.length][m2[0].length]; for (int i = 0; i < m1.length; i++) { for (int j = 0; j < m2[0].length; j++) { for (int k = 0; k < m2.length; k++) { res[i][j] %= Mod; res[i][j] += ((m1[i][k] % Mod) * (m2[k][j] % Mod)) % Mod; res[i][j] %= Mod; } } } return res; } }
这道题你会答吗?花几分钟告诉大家答案吧!
扫描二维码,关注牛客网
下载牛客APP,随时随地刷题
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次方也是如此。
有了上面的思路,不难写出下面的代码
最后注意:
有不足的地方,希望大家批评指正!