走法1：每次走1级台阶，一共走3步。(1步+1步+1步)
走法2：先走1级，再走2级。(1步+2步)
python3实现代码(表格内容为在leetcode上提交的反馈信息)
思路: 首先思考只差一步到达第n级台阶时的状态：因为我们一步可选择向上1级或者2级，所以要达到最终的状态前有2个子状态（子状态分别是a.站在第n-1级台阶和b.站在第n-2级台阶上）。由此得到我们算法的核心公式：
树的高度为N，节点个数近似于2的n次方，所以时间复杂度近似于O(2n)
如上图所示，我们发现方法1中很多地方被重复计算了（相同颜色代表着重复的部分），如果我们每算出一个颜色的方块的数值就记录下来，这样就减少了很多重复的计算。
此时空间复杂度为O(n)时间复杂度也为O(n)。
我们之前两个方法的核心的递归式f(n) = f(n-1) + f(n-2)是一个自顶向下求解的式子。
现在尝试一下自底向上的逻辑： 首先是下图示意的初始状态：
接下来迭代出3层楼梯：
然后是4层楼梯： 由此逐步累加到我们的目标第N层楼梯。 此时的思路是：
要达到状态n前有2个子状态（子状态分别是a.站在第n-1级台阶和b.站在第n-2级台阶上），
当在第n-1级台阶时，走一步1级到达最终状态；当在第n-2级台阶时，有两种方法到第n级台阶（走两步1级和走一步2级）。
完成迭代之后，往前移一层，如图a到图b变化的过程。
当前时间复杂度仍为O(n)，但空间复杂度降为O(1)。
个人认为自顶向下和自底向上有一个容易混淆的地方，但是我还没有看到有人讨论过这个问题（可能是只有我会混淆吧）
乘2是因为站在n-2时，有向上1级和向上2级可以选择，这在动态规划（自底向上）里是很自然的（所以有人说正常的思路应该是一步一步往上走的自底向上的求解方法）。
但是其实在递归求解里，当计算f(n-1)时，会把站在n-2级台阶再向上1级的情况包含进去，所以f(n-2)就不需要乘2了。