消除递归典型应用2------N阶台阶问题

问题描述：一个人可以一步走1或2或3级台阶，问到N级台阶共有多少种走法，输出各种走法的路径？
分析：如果只是统计走法个数，简单的f(n)=f(n-1)+f(n-2)+f(n-3)【n>=3】即可，但要输出路径，如果考虑递归的话，显然会内存消耗非常大，而循环求解的话，因为每一步都能利用已经存储的值，所以效率更好一些。
具体参见代码：

 

package Staticsteps;

import java.util.ArrayList;
import java.util.List;
//存储路径用的结果节点 里面放了存储ArrayList的ArrayList
public class ResultNode {
    private  ArrayList<ArrayList<Integer>> resultList =null;
    public ResultNode(){
        resultList = new  ArrayList<ArrayList<Integer>>();
    }
    
    public ArrayList<ArrayList<Integer>> getResultList(){
        return resultList;
    }
}

 

 

package Staticsteps; 

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;


public class Staticsteps {

    public static void main(String[] args){
        
        Scanner scanner = new Scanner(System.in);
        int k = scanner.nextInt();
        System.out.println("The result roads is :");
        long startTime = System.currentTimeMillis();
        if (k>0)
            print(getResultRoad(k));
        long endTime = System.currentTimeMillis();
        System.out.println("Totally using "+(endTime-startTime)+" milliseconds");
    }
    
    public static ResultNode[] getResultRoad(int k){
        ResultNode[] result = null ;
        result = new ResultNode[k+1]; 
        
        //f(n)=f(n-3)+f(n-2)+f(n-1)
        for(int i = 0;i<k+1;i++){
            int m =0;
            result[i] = new ResultNode();
            if(i==0){
                ArrayList<Integer> alist = new ArrayList<Integer>();
                alist.add(0);
                result[0].getResultList().add(alist) ;
            }
            if(i-1>=0){//求f(n-1)
                while(result[i-1]!=null
                        &&result[i-1].getResultList().size()>0
                        &&m<result[i-1].getResultList().size()){
                    
                    ArrayList<Integer> p = (ArrayList<Integer>) result[i-1].getResultList().get(m).clone();
                    p.add(i);
                    result[i].getResultList().add(p);
                    m++;
                }
                m=0;
            }
            
            if(i-2>=0){//求f(n-2)
                while(result[i-2]!=null
                        &&result[i-2].getResultList().size()>0
                        &&m<result[i-2].getResultList().size()){
                    
                    ArrayList<Integer> q = (ArrayList<Integer>) result[i-2].getResultList().get(m).clone();
                    q.add(i);
                    result[i].getResultList().add(q);
                    m++;
                }
                m=0;
            }
            
            if(i-3>=0){//求f(n-3)
                while(result[i-3]!=null
                        &&result[i-3].getResultList().size()>0
                        &&m<result[i-3].getResultList().size()){
                    
                    ArrayList<Integer> z = (ArrayList<Integer>) result[i-3].getResultList().get(m).clone();
                    z.add(i);
                    result[i].getResultList().add(z);
                    m++;
                }
                m=0;
            }
            
        }
        return result;
    }
    //打印路径个数和具体路径
    public static void print(ResultNode[] result){
    
            System.out.println("------reach to "+(result.length-1)+" totally has "+result[result.length-1].getResultList().size()+" roads------");
            
            for(int i =0;i<result[result.length-1].getResultList().size();i++){
                
                for(int j =0;j<result[result.length-1].getResultList().get(i).size();j++)
                    System.out.print(result[result.length-1].getResultList().get(i).get(j)+" ");
                
                System.out.println();
            }
            
    }
    //复制上一步的链表
    public  Object clone() {
        Object o =null;
      try{
        
          o=(ArrayList<Integer>)super.clone();
         
      }catch(CloneNotSupportedException e) {
             
          System.out.println(e.toString());
         
      }
   
      return o;
    }
    
    
}

 

 

说明：思考过程，想说简单的递归解法，然后想办法消除递归就可以，里面的clone方法是复用上一步计算结果的关键。