对于这个题目，看看大家有什么效率更高的算法

其实走法的种数很多的时候，内存肯定很难将所有的结果都保存，而通过将结果阶段性保存到一个在硬盘的文件上，例如：当List里的走法达到1000，就将List里的结果输出到文件中并将List清空。我想这样肯定能够解决内存的问题。而当你要运行的N很大的时候，我想时间不是问题，而内存才是大问题，因为这关系到你的程序能不能在你的机子上跑，如果连跑都跑不起来，那谈时间就没用了。所以我觉得kimmking的方法至少能解决内存的问题。

兄弟，f(29)的所有走法的结果文件就达到了500M+，文件读写很成问题啊

但是就我现在机子的JVM来看，f（23）就跑不起来了，至少写进文件可以跑到了f（29）甚至更大吧。反正如果真的要把结果存储，然后再将结果打印的话，我觉得除了写进硬盘，好像没有其他解决的方法了。

能直接运行 上限23 不是说我算法效率不高  是因为我保存了从1开始到N的全部路径 这样就占掉太多内存了 如果只保存n-1 n-2 n-3 n-4 这4个值的路径的话   会提高n上限值，这个算法的时间效率肯定高于递归的 因为有了重复值记录。另外，只要更改jvm的设置，显然n上限值能提高。但n>24之后走法太多，这样内存中要保留有太多的链表数据，所以，解决的办法只能是利用io读写解决内存大小瓶颈，但这样的话会造成时间成本过大。这种递归类题目n值不能取太大 比如N=100的时候  恐怕一般的机器链硬盘搭上都很难说够不够了。

我写的算法23默认jvm配置 没有问题

但24就会OOM ,往后每大一个数字 数据量都是成倍增长，所以这个题目吧 重点还是改进下时间复杂度，消除递归。要是改空间的话，效果不太大，而且时间成本会急剧增加。

Consider using Iterator to generate the next result upon request, get the next result, do something with it, then get the next one again. This idea has been used in permutation related calculations.

嗯，不错，其实这个题只不过考的就是一个编程的思想和时间的效率，至于当N很大的时候，要把结果保存的话，他就会占一定的空间，这种基本上不用考虑，因为这个实用性应该不强，应该也不会有那个程序傻到要保存这些结果。

我觉得只要弄清楚fibonacci递归和非递归的效率差别　解这题就容易了
这里如果用top-down的递归效率是O(3^n) 因为迭代是这样的
f(n)=f(n-1)+f(n-2)+f(n-3)+O(1)
从大往小算这里面有很多重复计算　
如果用bottom-up的非递归 复杂度可以提高到O(n^2)
要打印所以解可能会不同　计算有多少种走法肯定bottom-up非递归要优很多

试试我这个　可能也没变好　这题我从面试出题者的角度考虑应该只算不同走法就好了　不应该打印路径

public class StairsWeak {
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		List<List<WeakReference<Integer>>> list = steps(20); 
		for (List<WeakReference<Integer>> i : list) {
			System.out.print("[");
			for (WeakReference<Integer> j : i) {
				System.out.print(j.get() + " ");
			}
			System.out.println("]");
		}
	}

	private static List<List<WeakReference<Integer>>> steps(int n) {
		//only 1 stair
		List<List<WeakReference<Integer>>> secLast = new ArrayList<List<WeakReference<Integer>>>();
		List<WeakReference<Integer>> tmp = new ArrayList<WeakReference<Integer>>();
		tmp.add(new WeakReference<Integer>(1));
		secLast.add(tmp);
		
		//2 stairs
		List<List<WeakReference<Integer>>> last = new ArrayList<List<WeakReference<Integer>>>();
		tmp = new ArrayList<WeakReference<Integer>>();
		tmp.add(new WeakReference<Integer>(1));
		tmp.add(new WeakReference<Integer>(1));
		last.add(tmp);
		
		tmp = new ArrayList<WeakReference<Integer>>();
		tmp.add(new WeakReference<Integer>(2));
		last.add(tmp);
		
		//3 stairs
		List<List<WeakReference<Integer>>> curr = new ArrayList<List<WeakReference<Integer>>>();
		tmp = new ArrayList<WeakReference<Integer>>();
		tmp.add(new WeakReference<Integer>(1));
		tmp.add(new WeakReference<Integer>(1));
		tmp.add(new WeakReference<Integer>(1));
		curr.add(tmp);
		
		tmp = new ArrayList<WeakReference<Integer>>();
		tmp.add(new WeakReference<Integer>(2));
		tmp.add(new WeakReference<Integer>(1));
		curr.add(tmp);
		
		tmp = new ArrayList<WeakReference<Integer>>();
		tmp.add(new WeakReference<Integer>(1));
		tmp.add(new WeakReference<Integer>(2));
		curr.add(tmp);
		
		tmp = new ArrayList<WeakReference<Integer>>();
		tmp.add(new WeakReference<Integer>(3));
		curr.add(tmp);
		if (n == 1) {
			return secLast;
		} else if (n == 2) {
			return last;
		} else if (n == 3) {
			return curr;
		} else {
			int count = 3;
			while (count != n) {
				System.gc();
				List<List<WeakReference<Integer>>> nList = new ArrayList<List<WeakReference<Integer>>>();
				for (List<WeakReference<Integer>> list : secLast) {
					tmp = new ArrayList<WeakReference<Integer>>();
					tmp.addAll(list);
					tmp.add(new WeakReference<Integer>(3));
					nList.add(tmp);
				}
				for (List<WeakReference<Integer>> list : last) {
					tmp = new ArrayList<WeakReference<Integer>>();
					tmp.addAll(list);
					tmp.add(new WeakReference<Integer>(2));
					nList.add(tmp);
				}			
				for (List<WeakReference<Integer>> list : curr) {
					tmp = new ArrayList<WeakReference<Integer>>();
					tmp.addAll(list);
					tmp.add(new WeakReference<Integer>(1));
					nList.add(tmp);
				}
				secLast = last;
				last = curr;
				curr = nList;
				
				count++;
			}
		}
			

		return curr;
	}
}

很抱歉的说，题目是明确说要打印路径的。