《剑指offer》青蛙变态上台阶的高级变形题

题目描述

一个人在上台阶，一次可以走一步或者两步，n级别台阶，请打印所有可能上法的具体执行步骤
输入：

3

输出：

[[1,1,1],[1,2],[2,1]]

代码格式：

class Solution{
public:
   vector<vector<int>> step(int n)
  { 
     
  }
}

解析思路

1. 利用递归，分两种情况:一次走一步和一次走两步
2. 函数参数设置为整型的台阶数n和vecotr类型的temp存放每次的执行结果
3. 全局变量定义一个双vector，用来存放多种跳台阶的方法
4. 对函数参数中的Vector类型的temp进行改进，改为引用类型，这样只用一个vector更加高效，也是递归回溯比较方便

代码

初级版

class Solution{
    public:
        void stepCount(int n, vector<int> temp)
        {
            if(n == 0)
            {
                result.push_back(temp);
            }
            else if(n < 0)
            {
                
            }
            else 
            {
                vector<int> temp1 = temp;
                temp1.push_back(1);
                stepCount(n-1, temp1 );
                
                vector<int> temp2 = temp;
                temp2.push_back(2);
                stepCount(n-2, temp2 );
            }
        }
};

高级版代码

class Solution{
    public:
        void stepCount(int n, vector<int> &temp)
        {
            if(n == 0)
            {
                result.push_back(temp);
            }
            else if(n < 0)
            {
                
            }
            else 
            {
                temp.push_back(1);
                stepCount(n-1, temp );
                temp.pop_back();
                
                temp.push_back(2);
                stepCount(n-2, temp );
                temp.pop_back();
            }
        }
};

双重vector的输出

    for(vector<vector<int> >::iterator iter=result.begin();iter !=result.end();iter++)
    {
        vector<int> vec_temp = *iter;
        for(vector<int>::iterator it = vec_temp.begin();it != vec_temp.end();it++)
        {
            cout << *it << " " ;
        }
        cout << endl;
    }

这道题类似于剑指offer34
完整代码见Github