Python程序：查找爬楼梯的方法数

假设我们有一个n阶楼梯，我们每次可以向上爬1阶或2阶。我们需要定义一个函数，返回爬上楼梯的唯一方法数。

步骤的顺序不能改变，因此每种不同的步骤顺序都算作一种方法。如果答案非常大，则将结果模 10^9 + 7

因此，如果输入为 n = 5，则输出将为 8，因为有 8 种唯一的方法：

• 1, 1, 1, 1, 1
• 2, 1, 1, 1
• 1, 2, 1, 1
• 1, 1, 2, 1
• 1, 1, 1, 2
• 1, 2, 2
• 2, 1, 2
• 2, 2, 1

为了解决这个问题，我们将遵循以下步骤：

• dp：一个大小为 n+1 的数组，并用 0 填充
• dp[1] := 1
• 对于 i 从 2 到 n+1，执行以下操作：
  • dp[i] := dp[i-1] + dp[i-2]
• 返回 dp 的最后一个元素模 m

让我们看看下面的实现，以便更好地理解：

示例

 实时演示

m =(10**9)+7
class Solution:
   def solve(self, n):
      dp=[0 for _ in range(n+2)]
      dp[1]=1
      for i in range(2,n+2):
         dp[i]=dp[i-1]+dp[i-2]
      return dp[-1] % m
ob = Solution()
print(ob.solve(5))

输入

5

输出

8

Arnab Chakraborty

更新于： 2020年10月5日

290 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习