有n级台阶,一个人每次上一级或者两级,问有多少种走完n级台阶的方法。为了防止溢出,请将结果Mod 1000000007

给定一个正整数int n,请返回一个数,代表上楼的方式数。保证n小于等于100000。

测试样例: 1 返回:1

Solutions

  快速写了一个代码,结果爆内存了:

# -*- coding:utf-8 -*-
class GoUpstairs:
    def countWays(self, n):
        # write code here
        if n == 1:
            return 1
        dp = [0 for _ in range(n + 1)]
        dp[0] = dp[1] = 1
        for i in range(2, n+1):
            dp[i] = dp[i-1] + dp[i-2]
        return dp[n] % 1000000007

  直接改用一个数来存结果,滚动数组?!

# -*- coding:utf-8 -*-
class GoUpstairs:
    def countWays(self, n):
        # write code here
        if n == 1:
            return 1
        a = 1
        b = 1
        c = 0
        for i in range(2, n + 1):
            c = a + b
            a = b
            b = c
        return c % 1000000007

References

  1. 12.4 台阶问题