首页 > 试题广场 >

上台阶

[编程题]上台阶

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

有一楼梯共m级，刚开始时你在第一级，若每次只能跨上一级或者二级，要走上m级，共有多少走法？注：规定从一级到一级有0种走法。

给定一个正整数int n，请返回一个数，代表上楼的方式数。保证n小于等于100。为了防止溢出，请返回结果Mod 1000000007的值。

测试样例：

返回：2

算法知识视频讲解

每天都要努力

这题用递归的斐波那契数列算***超时：
    public int countWays(int n) {
        // write code here
                
        if(n==0){
            return 0;
        }else if(n==1){
            return 1;
        }else if(n==2){
            return 2;
        }else{
            return countWays(n-1)+countWays(n-2);
        }  
        
    }
所以可以把他改成动态规划：
        public int countWays(int n) {
		// write code here

		int dp[]=new int [n];         

		dp[0]=0;
		dp[1]=1;
		dp[2]=2;
		if(n>2){
			for(int i=3;i<n;i++){
				dp[i]=(dp[i-1]+dp[i-2])%1000000007;
			}
		}
		return dp[n-1];

	}
dp[i]表示的是到第i个台阶有多少种跳法。

编辑于 2016-09-06 08:57:24 回复(12)

C/C++

zhaoying

/*
*n=2：只有1种跳法；
*n=3：两种跳法；
*n>3：假设跳N级的跳法有f(n)种，
* （1）第一次跳，跳1级，则剩下N-1级的跳法有f(n-1)种；
* （2）第一次跳，跳2级，则剩下N-2级的跳法有f(n-2)种；
* 所以：f(n) = f(n-1) + f(n-2)。
*/
class GoUpstairs {
public:
int countWays(int n) {
// write code here
int n0 = 1, n1 = 2;
int ret;
if (n == 1)
ret = 0;
if (n == 2)
ret = 1;
if (n == 3)
ret = 2;

for (int i = 4; i <= n; i++)
{
ret = (n0 + n1)%1000000007;

n0 = n1;
n1 = ret;
}
return ret;
}
};

编辑于 2016-09-03 15:47:17 回复(3)

cycleof

//设m级台阶有 a[m] 种走法，则有 a[m] = a[m-1] + a[m-2];因为到m阶只可能从m-1 和 m-2 这两个结果走过来。
//题目规定 1级 0 种 走法。2级易得有 1 种走法，3阶 2种。利用动态规划思想可解决问题。
class GoUpstairs {
public:
    int countWays(int n) {
        int a[100]={0,0,1,2};
        for(int i = 4; i <= n; i++)
            a[i] = (a[i-1] + a[i-2])%1000000007;
        return a[n];
    }
};

发表于 2017-07-26 17:52:35 回复(1)

我就是你想要的Offer

这个题就是斐波那契数列。我个人觉着遇到这种题，从最简单的底层开始，试一下，就会找到相应的规律了。


	classGoUpstairs {



	public:



	    intcountWays(intn) {



	        // write code here



	        ints[101];



	        s[0]=0;



	        s[1]=0;



	        s[2]=1;



	        s[3]=2;



	        for(inti=4;i<=n;i++)



	        {



	            s[i]=(s[i-2]+s[i-1])%1000000007;



	        }



	        returns[n];   



	    }



	};

发表于 2016-04-01 17:18:01 回复(7)

迷茫的烟火在升起

 思路：动态规划，从第三级开始，它的结果有第二级和第一级的结果相加得到。
推广到一般，则对于任意i>=3的台阶，它的方法数，从递推方程为： result[i] = result[i - 1] + result[i - 2]；
（其中result数组存的是该级的方法数） 考虑到会溢出，
将递推方程修改为： result[i] = result[i - 1] %1000000007+ result[i - 2]%1000000007;  import java.util.*;

public class GoUpstairs {
    public int countWays(int n) {
		if (n == 0) {
			return 0;
		}
		long[] result = new long[n + 1];
		result[0] = 0;
		result[1] = 1;
		for (int i = 2; i <= n; i++) {
			result[i] = result[i - 1] %1000000007+ result[i - 2]%1000000007;
		}
		return (int)(result[n] % 1000000007);
    }
}

编辑于 2016-03-20 10:19:03 回复(0)

Butterfliesflyaway↘

import java.util.*;
/*
在第一级台阶，从第一级到第一级有0种走法，f(1)=0
在第二级台阶，从第一级到第二级有1种走法，f(2)=1
在第三级台阶，从第一级到第三级有2种走法（一次上两级台阶，或一次上一级台阶），f(3)=2
实际就是斐波那契数列，第n级台阶的走法为从第n-1上一级台阶，或从n-2上两级台阶，f(n)=f(n-1)+f(n-2)
(PS：递归复杂度指数级，会超时；所以选择用循环实现，复杂度为O(n))
*/
public class GoUpstairs {
        if(n == 1) return 0;
        if(n == 2) return 1;
        if(n == 3) return 2;
        int a=1, b=2, tmp=0;
        for(int i=4; i<=n; i++) {
            tmp = (a+b)%1000000007;
            a = b;
            b = tmp;
        }
        return tmp;
    }
}

发表于 2019-03-09 21:10:19 回复(0)

C/C++

nbgao

class GoUpstairs {
public:
    int countWays(int n) {
        int dp[n];         dp[0] = 0;         dp[1] = 1;         dp[2] = 2;
        for(int i=3;i<n;i++) 
            dp[i] = (dp[i-1] + dp[i-2])%1000000007;
        return dp[n-1];
    }
};

发表于 2017-12-07 09:20:22 回复(0)

ChrisZZ

可以使用快速幂

class GoUpstairs{ typedef vector<long long> vec; typedef vector<vec> mat; public: /*  * 快速幂解法  */  int countWays(int n){
        n = n-1; if(n<=0){ return 0;
        } if(n<=2){ return n;
        } mod = 1000000007; mat base {{1,1}, {1,0}}; mat res = fast_matrix_power(base, n-2); return (2*res[0][0]+res[0][1])%mod;
    } /*  * 平庸解法  */  int cw(int n) {
        n = n-1; int dp[101];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2; if (n >= 3) { for (int i = 3; i <= n; i++) {
                dp[i] = (dp[i - 1] + dp[i - 2]) % mod;
            }
        } return dp[n];
    } private: int mod; /*  * 矩阵快速幂  */  mat fast_matrix_power(mat& m, int p){ mat ans(m.size(), vec(m[0].size(), 0)); // 构造单位矩阵eye  for(int i=0; i<ans.size(); i++){
            ans[i][i] = 1;
        } mat base = m; for(; p!=0; p>>=1){ if(p&1){
                matrix_mult(ans, base);
            }
            matrix_mult(base, base);
        } return ans;
    } /*  * 矩阵乘法  */  void matrix_mult(mat& m1, mat& m2){ // 对于矩阵维度的处理，仅做最基本的检查  assert(m1[0].size() == m2.size()); int p = m1.size(), q=m1[0].size(), r=m2[0].size(); mat res(p, vec(r, 0)); for(size_t i=0; i<p; i++){ for(size_t j=0; j<r; j++){ for(size_t k=0; k<q; k++){
                    res[i][j] = (res[i][j] + m1[i][k] * m2[k][j]) % mod;
                }
            }
        }
        m1.swap(res);
    }

};

编辑于 2017-09-12 20:46:44 回复(0)

wangwenbin

// 斐波那契数列
// f(n) = f(n-1) + f(n-2) n>3
import java.util.*;

public class GoUpstairs {
    public int countWays(int n) {
        // write code here
        if(n<=3){
            return n-1;
        }
        int a = 1;
        int b = 2;
        for(int i=4;i<=n;i++){
            b = a + b;
            a = b - a;
            b = b % 1000000007;
            a = a % 1000000007;
        }
        return b;
    }
}

发表于 2017-09-07 10:50:34 回复(0)

Java

牛客8605757号

既然你们都用了动态规划，那我分享一个能跑的递归算法

import java.util.*;
public class GoUpstairs {
       static int[] num = new int[100];
    public static int countWays(int n) {
        if(n == 0){
            return 0;
        }
        if(n == 1){
            return 0;
        }
        if(n == 2){
            return 1;
        }
        if(n == 3){
            return 2;
        }
        if(num[n-1] != 0){
            return num[n-1];
        }
        num[n-1] = (countWays(n-1)+countWays(n-2))%1000000007;
        return num[n-1];
    }
}

发表于 2017-06-17 10:59:10 回复(0)

H掠影

这题用递归会超时，我以为是大数问题，其实不是。用循环就不会超时了。

class GoUpstairs {

public:

int countWays(int n) {

// write code here

int a[101];

a[2]=1;

a[3]=2;

for(int i=4;i<=n;i++)

{

a[i]=(a[i-1]+a[i-2])%1000000007;

}

return a[n];

}

};

发表于 2017-03-31 21:41:51 回复(1)

冷色探戈

    // 递推
	public int countWays(int n) {

		int[] dp = new int[n+1];
		dp[0] = 0;
		dp[1] = 1;

		for (int i = 2; i <= n; i++) {
			dp[i] = (dp[i-1] + dp[i-2]) % 1000000007;
		}
		return dp[n];
	}

发表于 2017-03-31 00:49:56 回复(0)

阿里淘系技术部-营销工具

矩阵快速幂

发表于 2017-03-28 23:41:01 回复(0)

Java

王小叶

//个人觉得应该在最终的结果上Mod，不应该每做一步就Mod，你们觉得呢？
import java.util.*;

public class GoUpstairs {
    public int countWays(int n) {
        // write code here
        //dp[i]=dp[i-1]+dp[i-2]
        long[] dp = new long[n+1];
        dp[0]=0;
        dp[1]=0;
        dp[2]=1;
        dp[3]=2;
        int Mod=1000000007;
        for(int i=4;i<=n;i++){
            dp[i]=(dp[i-1]+dp[i-2])%Mod; //dp[i]=dp[i-1]+dp[i-2]
        }        
        return (int)dp[n]; //个人觉得应该是这样才对(int)(dp[n]%Mod)
    }
}

编辑于 2017-03-06 14:00:07 回复(3)

wsxoo

看了讨论区后，恍然大悟，原来可以用斐波那契数列的解法，解题的时候却没想到，只想到了用动态规划去解这道题

class GoUpstairs {
public:
    long long f[105][105];//f[i][j]表示第i步到达第j个台阶的方法数
    long long sum;
    int countWays(int n) {
        // write code here
        for(int i=0;i<=n;i++){
            f[1][i] = 0;
        }
        f[1][1] = 1;
        f[1][2] = 1;
        for(int i=2; i <=n;i++){//从第二步开始扫描
//我是以0级台阶作为起点的，而题目是以第1级台阶作为起点的，所以j只要扫描到n-1就可以了
            for(int j=2;j<=n-1;j++){//从第二级台阶开始扫描，到了第n-1级就停止
                f[i][j] = f[i-1][j-1] + f[i-1][j-2];
                if( f[i][j]>1000000007){
               	  f[i][j] = ( f[i][j]%1000000007);
            	}
            }
        }
        sum = 0;
        for(int i = 1 ; i <=n;i++){
            sum += f[i][n-1];
            if(sum>1000000007){
                sum = (sum%1000000007);
            }
        }
        return (sum%1000000007);
    }
};

发表于 2016-09-10 11:10:14 回复(0)

会呼吸旳痛

// (a+b)%m = （a%m + b%m）%m;
//防止溢出，中间结果mod
class GoUpstairs {
public:
    int countWays(int n) {
        // write code here
        
        long long a0=0;
        long long a1=1;
        long long a2;
        int i=0;
        while(i<n)
            {
            a2=a0%1000000007l+a1%1000000007l;
            a0=a1%1000000007l;
            a1=a2%1000000007l;
            i++;
        }
        return a0;
        
    }
};

发表于 2016-08-22 22:35:25 回复(0)

fight灬奋斗

class GoUpstairs {
public:
    int countWays(int n) {
       if(n==1)
            return 0;
        if(n==2)
            return 1;
		if(n==3)
			return 2;
        int a=1,b=2,i=3;
        while(i<n){
            b=(a+b)%1000000007;
            a=(b-a+1000000007)%1000000007;
            i++;
        }
        return b;
    }
};

发表于 2016-08-17 20:43:43 回复(0)

已注销

class GoUpstairs {
public:
//时间复杂度o(n),空间复杂度o(1);
    int countWays(int n) {
        // write code here
        if(n<=1) return 0;
        if(n==2) return 1;
        if(n==3) return 2;
        int pre=1;
        int next=2;
        int temp;
        for(int i=4;i<=n;i++)
        {
            temp=(pre+next)%1000000007;
            pre=next;
            next=temp;
        }
        return temp;
    }
};

发表于 2016-08-04 17:43:19 回复(0)

小小

#define Mod 1000000007
class GoUpstairs {
public:
	int cnt[300030];
    int countWays(int n) {
		if(n == 1) return 0;
		cnt[1] = 1; cnt[0] = 0;
		for(int i = 2;i <= n;++ i)
			cnt[i] = (((i >= 1 ? cnt[i - 1] : 0) + (i >= 2 ? cnt[i - 2] : 0))) % Mod;
		return cnt[n];
    }
};

发表于 2015-10-29 10:19:03 回复(3)

Winter.is.coming

首先这是个斐波拉数列，n为

1 2 3 4 5 ...

0 1 2 3 5 ...

public int countWays(int n) { int[] s=new int[101];  s[1]=0;s[2]=1;s[3]=2;  for(int i=4;i<=n;i++){
        s[i]=s[i-1]+s[i-2];  if(s[i]>1000000007)
            s[i]=s[i]%1000000007;  } return s[n]; }