0%

爬楼梯

发表于 阅读次数：

问题描述：

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。

  1. 1 阶 + 1 阶
  2. 2 阶
    示例 2：

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。

  1. 1 阶 + 1 阶 + 1 阶
  2. 1 阶 + 2 阶
  3. 2 阶 + 1 阶

解题思路：

斐波那契数列，即先手算出初始的两个到三个值，然后后面的每个数字产生的方法个数都可以有（n-1）+（n-2）因为爬楼梯每次都需要爬一个楼梯或者爬两个楼梯，所以是有规律的

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def climbStairs(self, n: int) -> int:
        if n==1:
            return 1
        else:
            dp=[1 for i in range(n)]
            dp[0]=1
            dp[1]=2
            for i in range(2,n):
                dp[i]=dp[i-1]+dp[i-2]
            return dp[n-1]