今天看到一道有趣的题目，如下
一个台阶总共有n级，如果一次可以跳1级，也可以跳2级。求总共有多少总跳法，并分析算法的时间复杂度
说它有趣，纯粹是因为看题目的时候看错了，把只能跳1级和2级看成了可以跳任意级，由此也得出了一个通解，虽然也比较简单，但挺有趣的。 按照原题，只要稍微列出几项便可以发现这其实是一个斐波那契数列，按照公式 n[i] = n[i-1]+n[i-2] 即可得出结果。 而如果不限制只能跳1级和两级，我们考虑： 假设当前在第1级楼梯，则接下来可以有n种选择，假设我们跳1级，则第2级有 n-1 种选择，以此类推。当跳1级的所有情况走完后（此时我们至少在第二级），我们需要重新回到第一级，然后跳两级。以此类推。 从上面分析可以得出两点：第一点，无论当前在哪一级，情况都是类似的，即在后面台阶上的操作相当于前面台阶操作的子操作。第二点，我们需要回溯。 很自然的，我们需要使用递归。并且，根据回溯后操作的特点，我们发现，递归中需要有循环
实现如下：
/** * @param int n 总台阶数 * @param int cur 当前所在台阶 * @param int count 当前可选跳法 **/ void runStep(int n, int cur, int &count) { // 到达最顶层，可选跳法递增。 // 注意前面我们已经保证了不会越界 if (cur == n) { count++; return; } int i = 0; // 每一级的选择为 n-i，注意是从1开始 for (i = 1; i <= n; i++) { // 我们需要保证当前的选择不会超过总的台阶数 if (n >= cur + i) runStep(n, cur+i, count); } }