上高楼

[编程题]上高楼

热度指数：3958 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

现在有一栋高楼，但是电梯却出了故障，无奈的你只能走楼梯上楼，根据你的腿长，你一次能走1级或2级楼梯，已知你要走n级楼梯才能走到你的目的楼层，请计算你走到目的楼层的方案数，由于楼很高，所以n的范围为int范围内的正整数。

给定楼梯总数n，请返回方案数。为了防止溢出，请返回结果Mod 1000000007的值。

测试样例：

返回：3

算法知识视频讲解

推荐

yayamma

之前也是一直超时，知道这个题目还有一种方法可以做，但是不知道如果将时间复杂度降低到O(logn)。今天看了程云老师的视频，才知道了如何下手：
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次方也是如此。

有了上面的思路，不难写出下面的代码

  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;
	}
}

最后注意：

题目要求模 1000000007，还有一点为了计算过程中，保证数据范围的有效，中间结果使用long。

有不足的地方，希望大家批评指正！

编辑于 2015-08-18 16:44:55 回复(1)

Java

Holiday_12138

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;
    }
}

发表于 2017-03-07 14:20:45 回复(0)