算法题（2）：三步问题

审题：需要输出小孩上楼梯的方式的数量（需要取模）

思路：

如果正面来思考这个问题会无从下手，因为我们的分类太多了，没有办法把大问题缩小。

但是如果反过来思考，小孩最后一步有几种情况，那就简单了，因为小孩只可以有三种步幅，分别是1步，2步，3步。

也就是说，小孩上到最后一级台阶的方式就是最后走1/2/3步的那三个台阶的方式数相加

f（n）= f(n-1) + f(n-2) +f(n-3)

此时我们的递归的式子就出来了

所以本题我们先尝试写递归的方法，如果超时了再换循环写法。

 方法一：递归

这个递归的逻辑就是每次都返回n-1台阶+n-2台阶+n-3台阶的方式数，最后递归到第一到三级台阶结束递归。

这里由于递归比较耗时间，所以没通过。那么我们换循环的方式来写

方法二：循环

 

利用数组进行数据存储，并把下标和台阶数对齐（这样子就可以直接返回台阶对应的元素内容了）

和递归从后往前递归不一样,循环需要从前往后依次算出走到对应台阶的方式数，最后全部计算出来后，再返回第n个台阶的方式数