首页 > 试题广场 >

上高楼

[编程题]上高楼

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

Madstorm

递推关系的题型都是基于Fibonacci序列的变种，这个题我们很容易发现它其实就是Fibonacci序列

Fibonacci序列的快速幂乘求解过程的基本思路是这样的

递推关系[a,b]=[b,a+b]

相当于[a,b]*[[0,1],[1, 1]]=[b,a+b],将 [[0,1],[1, 1]]设为base matrix

如果初始项为F(0)=[1 2]，F(n)=F(0)*base^n，此式即为Fibonacci通项的矩阵算法

对于快速幂乘，举个例子 2²⁰=4¹⁰=16⁵=16*16⁴=16*256²

矩阵的快速幂乘就是将基数不断自乘，以减少矩阵相乘次数。由于指数是log(N)递减的，每次需要常数时间，所以其复杂度是O(logN)：

附上通过的代码：

class GoUpstairs:

def countWays(self, n):

res=base=[[1,1],[1,0]]

surplus=[[1,0],[0,1]]

while(n>=2):

if n&1:

surplus=self.mutiply(surplus,res)

res=self.mutiply(res,res)

n=n>>1

res=self.mutiply(res, surplus)

return res[0][0]%1000000007

def mutiply(self,a,b):

temp=[[0,0],[0,0]]

for i in range(len(a)):

for j in range(len(b)):

for k in range(len(temp)):

temp[i][j]+=a[i][k]*b[k][j]%1000000007

return temp

发表于 2015-08-26 22:19:56 回复(0)

C/C++

nbgao

class GoUpstairs {
public:     void mul(long a[2][2], long b[2][2])     {         long t[2][2],mod=1e9+7;         t[0][0] = (a[0][0]*b[0][0]+a[0][1]*b[1][0])%mod;         t[0][1] = (a[0][0]*b[0][1]+a[0][1]*b[1][1])%mod;         t[1][0] = (a[1][0]*b[0][0]+a[1][1]*b[1][0])%mod;         t[1][1] = (a[1][0]*b[0][1]+a[1][1]*b[1][1])%mod;         memcpy(a, t, sizeof(long)*4);     }
    int countWays(int n) {
        long m[2][2] = {1,1,1,0}, e[2][2] = {1,0,0,1};
        
        while(n>1)
        {
            if(n&1)
                mul(e,m);
            mul(m,m);
            n>>=1;         }         mul(m,e);         return m[0][0];
    }
};

发表于 2017-12-14 01:35:32 回复(0)

Python

questRush

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

字节内推-内部职位查询-进度查询

//完美通过，还是参考楼上二位大神的

 class GoUpstairs

{

private:

static const int row = 2;

static const int col = 2;

int const Mod = 1000000007;

public:

long countWays(int n)

{

if (n < 1)

{

return 0;

}

if (n == 1 || n == 2)

{

return n;

}

long matrix[2][2] = { { 1, 1 }, { 1, 0 } };

DoubleArry res = GetmatrixPower(matrix, n - 2);

//return (int)(2 * res[0][0] % Mod + res[1][0] % Mod) % Mod;

return (2*res._arry[0][0]% Mod + res._arry[1][0]% Mod) % Mod;

}

private:

struct DoubleArry//用来聚合二维数组

{

long _arry[row][col];

DoubleArry()

{

for (int i = 0; i < row; ++i)

for (int j = 0; j < col; ++j)

_arry[i][j] = 0;

}

DoubleArry(long matrix[][col])

{

for (int i = 0; i < row; ++i)

for (int j = 0; j < col; ++j)

_arry[i][j] = matrix[i][j];

}

DoubleArry(const DoubleArry& d)

{

for (int i = 0; i < row; ++i)

for (int j = 0; j < col; ++j)

_arry[i][j] = d._arry[i][j];

}

DoubleArry& operator=(DoubleArry d)

{

swap(d._arry, _arry);

return *this;

}

};

//两个矩阵相乘

DoubleArry matrixMul(DoubleArry l, DoubleArry r)

{

DoubleArry ret;

for (int i = 0; i<row; ++i)

for (int j = 0; j<col; ++j)

{

for (int k = 0; k<row; ++k)

{

ret._arry[i][j] += ((l._arry[i][k] %= Mod)*(r._arry[k][j] %= Mod)) % Mod;

}

return ret;

}

//矩阵的n次方

DoubleArry GetmatrixPower(DoubleArry matrix, int n)

{

DoubleArry ret;

//DoubleArry ret = new DoubleArry(cellmtrix);

for (int i = 0; i<col; ++i)

//先把ret设为单位矩阵，相当于整数中的1

{

ret._arry[i][i] = 1;

}

DoubleArry tmp = matrix;

for (; n != 0; n >>= 1)

{

if ((n & 1) == 1)//只拿出二进制序列中为1的位来乘

{

ret = matrixMul(ret, tmp);

}

tmp = matrixMul(tmp, tmp);

}

return ret;

}

};

发表于 2016-08-04 15:04:06 回复(0)

稻草阳光

大家可以查看我的博客http://helloleex.blog.51cto.com/10728491/1769253有详细的思路

编辑于 2016-04-30 22:13:30 回复(3)

小刀初试

就是个斐波那契数列，要用矩阵乘法快速计算。

class GoUpstairs {
    void mul(long a[4],long b[4]){
        long t[4],mod=1e9+7;
        t[0]=(a[0]*b[0]+a[1]*b[2])%mod;
        t[1]=(a[0]*b[1]+a[1]*b[3])%mod;
        t[2]=(a[2]*b[0]+a[3]*b[2])%mod;
        t[3]=(a[2]*b[1]+a[3]*b[3])%mod;
        memcpy(a,t,sizeof(long)*4);
    }
public:
    int countWays(int n) {
        // write code here
        long m[4]={1,1,1,0},e[4]={1,0,0,1};
        for(;n>1;n>>=1){
            if (n&1) mul(e,m);
            mul(m,m);
        }
        mul(m,e);
        return m[0];
    }
};

发表于 2016-08-24 08:47:46 回复(1)

learner111111

import java.util.*;
//就是用矩阵快速幂法求裴波那契数列
public class GoUpstairs {
    public int countWays(int n) {
        long a[][]={{1,1},{1,0}};
        long res[][]={{1,0},{0,1}};
        while(n>0)
        {
            if((n&1)==1)
                res=digui(a,res);
            a=digui(a,a);
            n>>=1;
        }
        return (int)res[0][0];
    }
    public long [][] digui(long a[][],long res[][])
    {
        long res1[][]=new long[2][2];
        for(int i=0;i<2;i++)
            for(int j=0;j<2;j++)
                res1[i][j]=(res[i][0]*a[0][j]+res[i][1]*a[1][j])%1000000007;
        for(int i=0;i<2;i++)
            for(int j=0;j<2;j++)
                res[i][j]=res1[i][j];
        return res;
    }
}

发表于 2018-11-30 10:18:00 回复(0)

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)

哆啦不爱梦爱美食

class GoUpstairs {
public:
    void f(long a[2][2],long b[2][2]){
        long res[2][2]={0};
        for(int i=0;i<2;i++)
            for(int j=0;j<2;j++)
                for(int k=0;k<2;k++)
                    res[i][j]+=(a[i][k]*b[k][j])%1000000007;
        for(int i=0;i<2;i++)
            for(int j=0;j<2;j++)
                a[i][j]=res[i][j];

     }
    int countWays(int n) {
        long res[2][2]={2,1,0,0};
        long base[2][2]={1,1,1,0};
        if(n<3)
            return n;
        n=n-2;
        while(n){
            if(n&1)
                f(res,base);
            f(base,base);
            n=n>>1;
         }
        return (res[0][0])%1000000007;
    }
};

发表于 2018-08-09 20:31:18 回复(0)

云淡_风轻

class GoUpstairs {
public:
    int fact(int n,int a,int b){
        int t=1;
        int i,temp;
        if(a<b){
            temp=a;
            a=b;
            b=temp;
        }
        if(n==a)
            return 1;
        for(i=n;i>a;i--){
            t=t*i;
            if(b>1&&t%b==0){
                t=t/b;
                b--;
            }
        }
        while(b>1){
            t=t/b;
            b--;
        }
        return t;
    }
    int countWays(int n) {
        // write code here
        int i;
        int m,sum=0;
        for(i=0;i<=n/2;i++){
            m=fact(n-i,i,n-i-i);
            sum+=m;
        }
        return sum%1000000007;
    }
};

发表于 2017-07-18 11:13:04 回复(1)

懒羊羊13

void mul(long x[], long y[], long mod) {
	long a0[4],a1[4];
	for (int i = 0;i < 4;i++) {
		a0[i] = x[i];
		a1[i] = y[i];
	}
	x[0] = (a0[0] * a1[0] + a0[1] * a1[2]) % mod;
	x[1] = (a0[0] * a1[1] + a0[1] * a1[3]) % mod;
	x[2] = (a0[2] * a1[0] + a0[3] * a1[2]) % mod;
	x[3] = (a0[2] * a1[1] + a0[3] * a1[3]) % mod;

}
int countWays(int n) {
	// write code here
	long mod = 1000000007;
	if (n<0)
		return 0;
	if (n == 1 || n == 2)
		return n;
	long x[4] = { 1,0,0,1 }, a1[4] = { 1,1,1,0 };

	for (;n != 0;n >>= 1) {
		if (n & 1 != 0) {
			mul(x, a1, mod);
		}
		mul(a1, a1, mod);
	}

	long result = x[0] % mod;
	return result;
}

发表于 2017-06-10 16:08:28 回复(0)

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)

他大舅

//求大神指点，我的代码为啥是段错误
class GoUpstairs {
public:
    int fun(int n)
    {
        if(n==1)
            return 1;
        else if(n==2)
            return 2;
        else
        	return fun(n-1)+fun(n-2);
    }
    int countWays(int n) {
    return fun(n)/1000000007;
    }
};

编辑于 2016-06-07 10:46:42 回复(2)

CalvinZhu

斐波那契，f(n) = f(n-1)+f(n-2)

发表于 2015-08-04 11:02:30 回复(0)

Baymax

  为什么会超时............. 

  classGoUpstairs { 

  public: 

      intcountWays(intn) { 

          // write code here 

          if(1== n || 2== n) 

              returnn; 

          ints1=1,s2=1,s3=0; 

          for(inti=2;i<n;++i){ 

              s3 = s1 + s2; 

              s1 = s2; 

              s2 = s3; 

          } 

          returns3%1000000007; 

      } 

  };