题目：

有一段楼梯台阶有 15 级台阶，以小明的脚力一步最多只能跨 3 级，请问小明登上这段楼梯，有多少种不同的走法?

分析：

很明显，是一个递归问题。到n级台阶有“三种”方法：先到n-1级台阶，再跨1级；先到n-2级台阶，再跨2级；先到n-3级台阶，再跨3级。

明白这点之后，算法就呼之欲出了。

算法代码：

int goSteps(int stairs)
{
    if (1 == stairs) {
        return 1;
    } else if (2 == stairs) {
        return 2;
    } else if (3 == stairs) {
        return 4;
    } else {
        return goSteps(stairs - 1) + goSteps(stairs - 2) + goSteps(stairs - 3);
    }
}

测试代码：

//
//  main.cpp
//  goSteps
//
//  Created by Jiajie Zhuo on 2017/4/8.
//  Copyright © 2017年 Jiajie Zhuo. All rights reserved.
//

#include <iostream>

using namespace std;

int goSteps(int stairs);

int main(int argc, const char * argv[]) {
    cout << "Please enter the nubmer of stairs: ";
    int stairs;
    cin >> stairs;
    
    cout << "The method of up to " << stairs << " is " << goSteps(stairs) << endl;
    
    return 0;
}

总结：

这是一个典型的递归问题，斐波那契数列的衍生版。需要注意的一点就是，到n-2或者n-3级之后，都只能通过一次跨2级或者1次跨3级来到达n级台阶！不能分为跨两次1级或者跨1级再跨两级，因为这种情况已经在跨到n-1级或者跨到n-2级的时候包含了，再算就会重复。