leetcode70. 爬楼梯 🌟

1 class Solution:
2     def climbStairs(self, n: int) -> int:
3         g = 0
4         f = 1
5         while n > -1:
6             g = g + f
7             f = g - f
8             n -= 1
9         return g

1 class Solution:
2     def climbStairs(self, n: int) -> int:
3         a = 1
4         b = 1
5         for _ in range(n - 1):
6             a, b = b, a + b
7         return b
# https://leetcode-cn.com/problems/climbing-stairs/solution/70-climbing-stairs-dong-tai-gui-hua-fei-bo-na-qi-s

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

 1 class Solution:
 2     # 作者：QQqun902025048
 3     # 链接：https://leetcode-cn.com/problems/two-sum/solution/2-xing-python-dong-tai-gui-hua-by-knifezhu/
 4     
 5     # dp递归方程：到达当前楼梯的路径数 = 到达上个楼梯的路径数 + 到达上上个楼梯的路径数
 6     # 这里用一个元组 r 来储存（当前楼梯路径数，下一层楼梯路径数）
 7     # 利用 reduce 来代替for循环
 8     def climbStairs(self, n: int) -> int:
 9         from functools import reduce
10         return reduce(lambda r, _: (r[1], sum(r)), range(n), (1, 1))[0]

 1 class Solution:
 2     def climbStairs(self, n: int) -> int:
 3         return self.climbStairsImpl(n)
 4 
 5     def climbStairsImpl(self, n: int, memo={}) -> int:
 6         if n < 3:
 7             return n
 8         if n in memo:
 9             return memo[n]
10         else:
11             tmp = self.climbStairsImpl(n - 1, memo) + self.climbStairsImpl(n - 2, memo)
12             memo[n] = tmp
13             return tmp