题目：
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个或者3个台阶。你有多少种不同的组合可以爬到楼顶呢？返回组合列表数组
爬楼梯开拓下需求，这里先用递归好理解，加个缓存凑合用，例如共3层台阶，后面改成for 循环线性复杂度，耗内存，输出[[1,1,1],[2,1],[1,2],[3,]]结果!
直接上代码吧，就是在前三种上方式，追加最后一步数达到n就可以了，例如输入3,上两层[[1,1],[2,]]，追加成 [[1,1,1],[2,1]] 时间复杂度指数级,self.m加个缓存，兄弟们还有其他优秀解法可以交流一波！
方法一（递归加缓存）
class Solution(object):
def __init__(self):
self.m = {}
def add_end(self, arr, totalNum):
tmpArr = []
for innerItem in arr:
sum_ = sum(innerItem)
delta = totalNum - sum_
if delta == 3 or delta == 1 or delta == 2:
tmpArr.append(innerItem + [delta])
return tmpArr
def climbStairs(self, n):
"""
:type n: int
:rtype: list
"""
if n in self.m:
return self.m[n]
if n == 1:
return [[1, ]]
elif n == 2:
return [[1, 1], [2, ]]
elif n == 3:
return [[1, 1, 1], [2, 1], [1, 2], [3, ]]
else:
f1 = self.add_end(self.climbStairs(n - 1), n)
f2 = self.add_end(self.climbStairs(n - 2), n)
f3 = self.add_end(self.climbStairs(n - 3), n)
self.m[n] = f1 + f2 + f3
return self.m[n]
方法二（线性）：
class Solution2(object):
def add_end(self, arr, totalNum):
tmpArr = []
for innerItem in arr:
sum_ = sum(innerItem)
delta = totalNum - sum_
if delta == 3 or delta == 1 or delta == 2:
tmpArr.append(innerItem + [delta])
return tmpArr
def climbStairs(self, n):
"""
:type n: int
:rtype: list
"""
dp = [[] for _ in range(n)]
dp[0] = [[1, ]]
dp[1] = [[1, 1], [2, ]]
dp[2] = [[1, 1, 1], [2, 1], [1, 2], [3, ]]
if n == 1:
return dp[0]
elif n == 2:
return dp[1]
elif n == 3:
return dp[2]
for i in range(3, n):
dp[i] = self.add_end(dp[i - 1], i+1) + self.add_end(dp[i - 2], i+1) + self.add_end(dp[i - 3], i+1)
return dp[-1]
公式推导:
这里拓展了下,加个f(x-3),如果只允许1步，三步上台阶，就是f(x) = f(x - 1) + f(x - 3)，提前定义好f(1),f(2),f(3)
可能有小伙伴会疑问 f(x) = f(x - 1) + f(x - 2) 是怎么来的
首先假设张三爬10阶楼梯, 有f(10)种方法, 至于f(10)的具体实现不管, 我们不妨先思考以下这几个问题:
张三可以怎样爬到第10阶呢? 答: 他可以爬到第9阶再爬1阶, 或者爬到第8阶再爬2阶
张三从0阶到9阶有多少种方法呢? 答: f(9)
于是这样的式子顺理成章浮现在了你的眼前: f(10) = f(9) + f(8)
于是这样套娃下去, 早晚有一天会简化成一堆f(1)和f(2)相加, 我们只需要提前定义好f(1)和f(2)的值就可以了
