一共有n阶阶梯，我们可以一步走一阶，也可以一步走两阶，求一共有几种走法
第一次看到这个问题我想到了排列组合，奈何数学功底太差没有想出具体的解决方法… 既然没法用排列组合解决，那就尝试用其他方法，这里我选择用的是递归。首先我们假设共有40阶楼梯：
如果最后一步走的是1个阶梯， 那之前一定走到了第39个阶梯；如果最后一步走的是2个阶梯，那么之前一定只走到了38个阶梯（绝对不可能走到39阶,因为只有40阶， 最后一步走两阶）。同理， 在走到39阶前一步，也有两种可能：
只走了一阶，那么之前一定是走到了38阶；另一种是，走了两阶， 那么之前一定是走到了37阶。所以总结出一个规律： 走40阶的走法 = 走39阶的走法 + 走38阶的走法 走39阶的走法 = 走38阶的走法 + 走37阶的走法 走38阶的走法 = 走37阶的走法 + 走36阶的走法 … 走3阶的走法 = 走2阶的走法 + 走1阶的走法 走2阶的走法为2种（1、一步走1阶， 走两步；2、一步走两阶， 走一步 ） 走1阶的走法为1种（1、一步走1阶，走一步） 这里我们归纳一个函数，opt(n)表示走n阶阶梯的所有方法，出口为 n=1 或者 n=2 , 则：
在递归的过程中，出现很多的重复调用，如下图所示， 这大大的加大了时间复杂度，所以我们需要避免这种情况的出现，可以将每一次递归调用的值按顺序存入一个数组，下一次调用的时候直接使用数组的值即可。
当输入数字很大时， 递归和动规的时间对比就很明显了，大家可以自己试试。
#include <iostream> #include <vector> using namespace std; /**************************************************************************** * 函数功能： 通过递归的思想算出走num阶楼梯的走法（每次可走一阶，也可走两阶） * 输入参数： 楼梯的阶数 * 返回值： 总走法 *****************************************************************************/ int rec_climbstairs(int num) { if(num < 0) { cout<<"输入参数有误， 输入参数应大于0"<<endl; return -1; } if(num== 0 | num == 1 || num == 2) { return num; } else { return (rec_climbstairs(num - 1) + rec_climbstairs(num - 2)); } } /**************************************************************************** * 函数功能： 通过动态规划的思想算出走num阶楼梯的走法（每次可走一阶，也可走两阶） * 输入参数： 楼梯的阶数 * 返回值： 总走法 *****************************************************************************/ int opt_climbstairs(int num) { if(num < 0) { cout<<"输入参数有误， 输入参数应大于0"<<endl; return -1; } vector<int > dp_arr; dp_arr.push_back(0); dp_arr.push_back(1); dp_arr.push_back(2); for(int i=3; i<=num; i++) { int sum = 0; sum = dp_arr.at(i-1) + dp_arr.at(i-2); dp_arr.push_back(sum); } int rv = dp_arr.at(num); return rv; } int main() { int num; cin>>num; if(rec_climbstairs(num)) cout<<"使用递归得出[爬"<<num<<"阶]楼梯共有："<< rec_climbstairs(num)<<"种方法。"<<endl; if(opt_climbstairs(num)) cout<<"使用动态规划得出[爬"<<num<<"阶]楼梯共有："<< opt_climbstairs(num)<<"种方法。"<<endl; return 0; }