Python实现"爬楼梯"的方法

发布于:2021-09-15 22:02:44

你需要攀爬一个有n个台阶的梯子


每一次你只能走1步或者两步,计算有多少中不同的登顶方式


注意:n必为正整数



Example 1:


Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:


Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step


1:动态规划(参考:https://www.cnblogs.com/z941030/p/5615554.html;https://www.cnblogs.com/springfor/p/3886576.html)

假设梯子有n层,那么如何爬到第n层呢,因为每次只能怕1或2步,那么爬到第n层的方法要么是从第n-1层一步上来的,要不就是从n-2层2步上来的,所以递推公式非常容易的就得出了:


dp[n] = dp[n-1] + dp[n-2]


def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
if n<=2:
return n
temp_list = [0,1,2]
for i in range(3,n+1):
temp_list.append(temp_list[-1]+temp_list[-2])
return temp_list[-1]

2:递归(错误:超出时间限制)

def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
sum = 0
if n<=2:
return n
sum += self.climbStairs(n-1)
sum += self.climbStairs(n-2)
return sum

算法题来自:https://leetcode-cn.com/problems/climbing-stairs/description/

相关推荐