假设你正在爬楼梯。需要?n?阶你才能到达楼顶。
每次你可以爬?1?或?2?个台阶。你有多少种不同的方法可以爬到楼顶呢？
?根据题目要求，每次只能爬一阶或者二阶，那么当你在第n阶时你前一步就只能是第n-1阶或者第n-2阶。所以我们可以得到递归式：
f（n）=f（n-1）+f（n-2）其中n>=2
于是我们可以得到我们第一种方法的代码求解：
def climbStairs(self, n: int) -> int:
? ? if n == 0 or n == 1:
? ? ? ? return 1
? ? return self.climbStairs(n - 1) + self.climbStairs(n - 2)
但是该方法超时了，因为有很多阶计算重复了，所以我们把每一阶所需的步数存入数组，用空间换时间：
def climbStairs(self, n: int) -> int:
? ? def dfs(i: int, memo) -> int:
? ? ? ? if i == 0 or i == 1:
? ? ? ? ? ? return 1
? ? ? ? if memo[i] == -1:
? ? ? ? ? ? memo[i] = dfs(i - 1, memo) + dfs(i - 2, memo)
? ? ? ? return memo[i]
? ? # memo: [-1] * (n - 1)
? ? # -1 表示没有计算过，最大索引为 n，因此数组大小需要 n + 1
? ? return dfs(n, [-1] * (n + 1))
但是这样的方法又存在过多的判断，我们可以自底向上，去除很多判断，代码可以优化为：
def climbStairs(self, n: int) -> int:
? ? dp = [0] * (n + 1)
? ? dp[0] = dp[1] = 1
? ? for i in range(2, n + 1):
? ? ? ? dp[i] = dp[i - 1] + dp[i - 2]
? ? return dp[-1]
当自底向上的时候，我们发现f（n）始终只依赖两项就是f（n-1）和f（n-2），于是我们只需要两个数：
def climbStairs(self, n: int) -> int:
? ? a = b = 1
? ? for i in range(2, n + 1):
? ? ? ? a, b = b, a + b
? ? return b。