Leetcode 70 题
有人问我：烤冷面你这两周怎么总搞简略题？我想说：一步一步来～
题干简述
给定：
- 假如你正在爬楼梯，须要爬 n 阶你能力达到楼顶。
- 每次你能够爬 1 或 2 个台阶。
要求：计算出有多少种爬楼梯的形式。
解题思路
如果咱们放大视线（把大问题化为小问题），爬到第 n 阶台阶有两种形式：
- 从 n-1 阶爬一级台阶
- 从 n-2 阶爬两级台阶
用公式表白：dp[n] = dp[n−1] + dp[n−2]，其中的特例是：dp[0]=1 和 dp[1]=1。
嚯！这不就是 LeetCode 509(斐波那契数列) 么。
代码实现
class Solution:
def climbStairs(self, n: int) -> int:
if n <= 2:
return n
dp = [0]*(n+1)
dp[0] = 1
dp[1] = 1
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]复杂度
工夫复杂度 O(n)，空间复杂度 O(n)。
关注公众号：「侵蚀脚本」，退出交换群。
文章归档：烤冷面讲算法系列
转载申明：本文章容许转载，原文地址：「动静布局」LeetCode 70(爬楼梯)