用 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
• 对于范围为 2 到 n+1 的 i，执行
  • dp[i]:= dp[i-1]+dp[i-2]
• 返回 dp mod 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

相关文章

• Python - 使用交替的 0 和 1 初始化列表
• Python 中元组列表到字典的转换
• Python - 从两个列表中配对，使得成对的元素不相同
• 使用 Python 和 SQLite 的 SQL
• 使用 pytrie 模块在 Python 中进行前缀匹配
• 创建和访问 Python 包
• 如何使用正则表达式和数据类型选择多个 DataFrame 列
• 如何在 Pandas 中查找和过滤重复行?
• 用 Python 编写程序以正确的顺序查找机场?
• 如何在 Python Pandas 中使用字典顺序切片选择数据子集?

有用资源

• python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/