专业的聊城网站优化,上海建站模板源码,网上开店策划书,门户网站开发要求70. 爬楼梯 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢#xff1f; 思路#xff1a; 考虑: 假设现在已经爬到了某一阶台阶#xff0c;那是如何到达这里的呢#xff1f;可能是从前一阶台阶爬上来的 思路 考虑: 假设现在已经爬到了某一阶台阶那是如何到达这里的呢可能是从前一阶台阶爬上来的也可能是从前两阶台阶爬上来的。也就是说从第 i 阶楼梯可以从第 i - 1 或者 i - 2 阶楼梯爬上来。因此有一个递推公式d[i] d[i-1] d[i-2]
1. 动态规划
# 1. 动态规划
class Solution(object):def climbStairs(self, n)::type n: int:rtype: intif n 1:return 0if n 1:return 1elif n 2:return 2d [0] * (n 1) # 初始化列表长度为 n 1, 所有元素的值为 0, 用来存储每个台阶的爬法数d[1] 1 # 第 1 阶只有 1 种方式d[2] 2 # 第 2 阶有 2 种方式# 从第 3 阶开始根据递推公式计算每个台阶的爬法数for i in range(3, n 1):d[i] d[i - 1] d[i - 2]# 返回到达第 n 阶的方法数return d[n]时间复杂度: O(n)空间复杂度: O(n)
空间优化版本
class Solution(object):def climbStairs(self, n)::type n: int:rtype: intif n 1:return 0if n 1:return 1elif n 2:return 2# 使用两个变量来存储前两阶的爬法数prev1, prev2 2, 1 # prev1 是 d[i-1], prev2 是 d[i-2]for i in range(3, n 1):current prev1 prev2prev2 prev1prev1 current# 返回最终的结果return prev1时间复杂度: O(n)空间复杂度: O(1)
2. 递归法
# 2. 递归(ps: 递归法在leetcode中运行会超时)
class Solution(object):def climbStairs(self, n)::type n: int:rtype: intif n 1:return 1return self.climbStairs(n-1) self.climbStairs(n-2)时间复杂度: O(2^n)递归调用的过程形成了一个类似于树的结构每一层都会有两个递归分支导致时间复杂度呈指数级增长。总的递归调用数大约为 2^n因此时间复杂度是 O(2^n)。空间复杂度: O(n)递归调用会在系统栈中占用空间每一次递归都会添加一个新的栈帧直到到达基准情况n 1。最深的递归调用栈的深度为 n因为递归每次减少 1 或 2所以空间复杂度是 O(n)。
