我要招人

去企业版

首页 > 试题广场 >

上台阶

[编程题]上台阶

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

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

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

测试样例：

返回：2

算法知识视频讲解

Java

青石落鼓

public static int countWays(int n) {
    int r[] = new int[n + 1];
    r[1] = 1;
    for (int i = 2; i <= n; i++) {
        r[i] = (r[i - 1] + r[i - 2]) % 1000000007;
    }
    return r[n];
}

发表于 2018-06-19 10:23:56 回复(0)

Java

安徒生的谎言

import java.util.*;

public class GoUpstairs {
    public int countWays(int n) {
        // write code here
        int[] dp=new int[n+1];
        dp[1]=1;
        dp[2]=1;
        for(int i=3;i<=n;i++){
            dp[i]=(dp[i-1]+dp[i-2])%1000000007;
        }
        return dp[n];
    }
}

发表于 2018-01-27 11:38:04 回复(0)

Java

缺个offer

import java.util.*;

public class GoUpstairs {

public int countWays(int n) {

if(n <= 1){

return 0;

}

if(n == 3){

return 2;

}

if(n == 2){

return 1;

}

int a = 1;

int b = 2;

int temp = 0;

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

temp = (a+b)%1000000007;

a = b;

b = temp;

}

return temp;

}

发表于 2017-07-29 22:26:27 回复(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)

Java

java的神秘男友script

import java.util.*;

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

只对结果取余有问题。。。所以还是每一次。。

发表于 2017-03-09 02:01:38 回复(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)

Java

Holiday_12138

//斐波那契 非递归
import java.util.*;

public class GoUpstairs {
    public int countWays(int n) {
        int res=0;
        if(n==1) res=0;
        if(n==2) res=1;
        if(n==3) res=2;
        int p=1,q=2;
        for(int i=4;i<=n;i++){
            res=(p+q)%1000000007;
            p=q;
            q=res;
        }
        return res;
    }
}

发表于 2017-02-23 16:00:17 回复(0)

Java

詆調壹點

import java.util.*;
public class GoUpstairs {
    public int countWays(int n) {
        int dp[] = new int[n];
        dp[0] = 1;
        dp[1] = 1;
        for(int i=2;i<n;i++)
            dp[i]=dp[i-1]%1000000007+dp[i-2]%1000000007;
        return dp[n-1]%1000000007;
    }
}

发表于 2016-09-10 01:16:43 回复(0)

Java

悠佑

一开始考虑用long型结果溢出了，后来想到Thinking in java 还是哪本书提到过BigDecimal，果然适用于无敌大的数啊。
import java.util.*;
import java.math.BigDecimal;

public class GoUpstairs {
    public int countWays(int n) {
        // write code here
        // write code here
        BigDecimal firstPrev ;
        BigDecimal secondPrev ;
        if(n ==1) return 0;
        if(n ==2) return 1;
        secondPrev =new BigDecimal(1);
        if(n == 3) return 2;
        firstPrev = new BigDecimal(2);
        BigDecimal result = new BigDecimal(0);
        for(int i=4; i<= n ;i++){
            result = firstPrev.add(secondPrev);
            secondPrev = firstPrev;
            firstPrev = result;
        }
        BigDecimal last = result.remainder(new BigDecimal(1000000007));
        return  last.intValue();
    }
}

发表于 2016-07-09 09:33:58 回复(0)