【LeetCode 每日一题】70. 爬楼梯 | 手写图解版思路 + 代码讲解

-By-Zero-:
纯数学爱好者路人，这个在数学里是经典的斐波那契数列诶，f（n）=f（n-1）+f（n-2）

【回复】是的，也是编程里的递归经典入门题~
【回复】没有哪个学科可以离开数学，计算机尤其如此
【回复】我记得我小学学而思就学过斐波那契数列，但都是很简单的那种
我想住大别野:
你好，请问n阶楼梯，每次可以爬1到m层，并且我有个习惯就是这次爬的台阶数不能和上次以及上上次相同，那么有多少种不同的方法呢

【回复】感觉状态表示可以加一个维度，最后一次爬j个台阶爬到第i个台阶的方案数
qdzwxe:
小内存是直接解差分方程写通项吧[抠鼻]

【回复】小内存滚动数组呗 当然通项可以无敌的o1时间复杂度
【回复】解出来是个无理数，也就是计算机表示不出来
哔哔哩哩首席官:
up主，如果爬楼梯的次数不固定，给定一个数组arr 1 3 5 7，爬到n阶这种怎么搞

【回复】1，3，5，7的话那么第n级台阶等于第n-1，n-3，n-5，n-7级台阶爬法之和
嘉园の恶霸:
第一反应dp，第二反应不就是斐波拉契[滑稽]

离战场还有几英里:
矩阵快速幂 可以logn求解 直接抄个通项公式大能log1

靛字君:
爬楼梯，其实也是一种完全背包不过物品的价值被定成1｜｜2了

【回复】回复 @流年的榴莲o :用背包的意义在于如果把题目改成一次能爬1层2层...m层，如果改成这样就只能用背包写了，哈哈
【回复】回复 @流年的榴莲o :背包的一个考点就是遍历顺序，即物品和背包先遍历哪个。我是先写了爬楼梯后面学背包的时候才拿背包去套爬楼梯的
【回复】回复 @靛字君 :算了纠结这个也没啥用[喜极而泣]，不过跑完全背包要满两倍
NO3-:
我做的时候根本没想到递归，我是用排列组合算出通项来做的

不朽的拉普拉斯:
能不能用不动点法算出来通项公式，然后直接写通项公式？

_等春夏_:
直接一推就是斐波拉契[笑哭] 而且前面一题也是斐波拉契