leetcoe 斐波那契初探 70. Climbing Stairs
原创
这个经典了， 我记得以前看过清华版数据结构第一章， 整章都是讲这个的。 写的非常不错， 可惜没有PYTHON版的， 希望什么时候出一版python的哈哈。 《天才基本法》里也有问这个上梯子的桥段。
题目，
You are climbing a staircase. It takes n steps to reach the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
非常经典的递归问题， 有两个递归基， 即 n== 1, 和 n ==2， n>2的情况都可以拆解成更低n的问题， 比如 f(n=3) = f(3-1) + f(3-2), 即在上三个台阶时候， 你是先上一个，还是先上两个。
f(n = 5) = f(4) + f(3) , f(4) = f(3) + f(2), f(3) = f(2) + f(1),
先看最直观的答案：
class Solution(object):
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
if n == 1：
return 1
if n == 2:
return 2
return self.climbStairs(n-1) + self.climbStairs(n-2) 思路是对的， 但是n==44的时候就已经超时， 原因可以看上面f(n == 5)的分解， 太多重复冗余的计算。
让我们通过牺牲空间来换取时间， 有那么多冗余的， 那我们把已经算过的值记下来就好了，这里就用字典记 {n: steps}的组合：
class Solution(object):
def climbStairs(self, n, memo = {}):
"""
:type n: int
:rtype: int
"""
if n in memo:
return memo[n]
if n == 1:
return 1
if n == 2:
return 2
ans = self.climbStairs(n-1) + self.climbStairs(n-2)
memo[n] = ans
return ans虽然这里省略了重复计算， 但是重复查询次数依然很多， 那么让我们更近一步， 寻找空间和时间兼顾的， 在最终答案前， 先看动态规划 （https://blog.csdn.net/fuxuemingzhu/article/details/51290778）：
class Solution(object):
def climbStairs(self, n, memo = {}):
"""
:type n: int
:rtype: int
"""
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[-1]从这个动态规划中， 我们可以发现， 其实只有一位前和两位前的值， 需要存储，那么就可以简化成空间压缩DP， 或者叫迭代法之类的，
class Solution(object):
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
first = second = 1
for n in range(n):
first, second = second, first + second
print(first,second)
return first迭代时一直往前，所谓的bottom-up。 递归时从最终问题往前回溯， 所谓的top-down
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
腾讯云开发者
