消除递归典型应用2-N阶台阶有关问题
消除递归典型应用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方法是复用上一步计算结果的关键。