0070. 爬楼梯

0070. 爬楼梯 #

  • 标签:动态规划
  • 难度:简单

题目大意 #

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?

解题思路 #

先来看一下规律:

第 1 阶台阶:1 种方法(从 0 阶爬 1 阶)

第 2 阶台阶:2 种方法(从 0 阶爬 2 阶,从 1 阶爬 1 阶)

第 i 阶台阶:从第 i-1 阶台阶爬 1 阶,或者从第 i-2 阶台阶爬 2 阶。

则推出递推公式为:F(i) = F(i-1) + F(i-2)

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1 or n == 2:
            return n
        f1 = 1
        f2 = 2
        for i in range(2,n):
            f3 = f1 + f2
            f1 = f2
            f2 = f3
        return f3
本站总访问量  次  |  您是本站第  位访问者