有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