我要招人

去企业版

首页 > 试题广场 >

上台阶

[编程题]上台阶

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

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

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

测试样例：

返回：2

算法知识视频讲解

Python

离疏

class GoUpstairs:
    def countWays(self, n):
        method=[0,0,1,2,3]
        for i in range(5,101):
            method.append(method[i-1]+method[i-2])#动态规划
        return method[n]%1000000007

发表于 2018-07-17 17:40:31 回复(0)

Python

华科平凡

python solution:

class GoUpstairs:
    def countWays(self, n):
        res = [1, 1]
        while len(res) < n:
            res.append(res[-1] + res[-2])
        return res[-1] % 1000000007

编辑于 2017-09-12 14:40:54 回复(1)

Python

HappyFlora

这样写为什么通不过呢？错误提示：请检查是否存在数组越界等非法访问情况

class GoUpstairs:
def countWays(self, n):
    if n<=1:
        return 0
    elif n<=3:
        return n-1
    else:
        a,b=1,2
        for i in range(4,n+1):
            temp=a+b
            a=b
            b=temp
        return b%1000000007

发表于 2017-05-18 17:09:51 回复(0)

Python

|虫|二|

class GoUpstairs:
    def countWays(self, n):
        # write code here
        f=[0,1]
        for i in range(2,n+1,1):
            f.append(f[i-1]+f[i-2])
        return f[n]%1000000007

use f[n]=f[n-2]+f[n-1], initial with f[0,1], just append each step's result and return f[n]

发表于 2017-05-11 22:06:49 回复(0)

Python

牛客4692560号

'''动规问题'''

class GoUpstairs:

def countWays(self, n):

# write code here

if(n==1):

return 0

elif(n==2):

return 1

else:

step=[0]*n

step[0]=1

step[1]=1

for i in range(2,n):

step[i]=step[i-1]+step[i-2]

return step[-1]%1000000007

发表于 2017-04-26 18:35:46 回复(0)

Python

不是码农

斐波那契序列法f(n)=f(n-1)+f(n-2),这里放置溢出，所以对结果做一个取模运算
class GoUpstairs:
    def countWays(self,n):
        # write code here
        l=[0,1,2]
        for i in range(n-3):
            l.append(l[-1]%1000000007+l[-2]%1000000007)
        return l[n-1]%1000000007

发表于 2016-09-04 23:20:23 回复(0)

Python

NKnobus

## python代码实现（python 3.5.2验证通过）
class GoUpstairs:
    """非递归方法"""
    def CountWays(self, n):
        # write code here
        if n < 1:
            return 0
        res = [0, 1, 2]
        if n > 3:
            for i in range(3,n):
                res.append(res[i-1] % 1000000007 + res[i-2] % 1000000007)
        return res[n-1] % 1000000007

    """递归方法"""
    def CountWaysRecursion(self, n):
        # write code here
        if n <= 1:
            return 0
        if n == 2:
            return 1
        if n == 3:
            return 2
        if n > 3:
            return (self.CountWaysRecursion(n-1)%1000000007 +
                    self.CountWaysRecursion(n-2)% 1000000007) % 1000000007

if __name__ == "__main__":

    maxNumStairs = 100
    print("num stairs: (Dynamic Results,Recursion Results)")
    for cnt in range(1,maxNumStairs): ## 1-100 staors
        stairs = GoUpstairs()
        res = stairs.CountWays(cnt)
        resRecursion = stairs.CountWays(cnt)
        print(" %d stairs: (%d, %d)" % (cnt, res, resRecursion))

编辑于 2016-08-09 15:05:45 回复(0)