「动态规划」LeetCode 70(爬楼梯)
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(爬楼梯)