上高楼

[编程题]上高楼

热度指数：4090 时间限制：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)

Python

离疏

# -*- 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

发表于 2018-10-05 13:34:24 回复(0)

Python

0x100000001b3

# -*- 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

编辑于 2017-04-02 18:46:39 回复(0)