面接プログラミング問題拾い(04)---階段を上るにはいくつの方法がありますか

子供は1つのN段の階段に登って、彼は一度に1階、2階あるいは3階を歩くことができて、それではN段を歩き終わってどれだけの方式があります.
自然な考えは再帰を使うことです.

public class Test04 {

	public static int countWays(int n) {
		if(n < 0) {
			return 0;
		}
		else if(n == 0) {
			return 1;
		}
		else {
			return countWays(n - 1) + countWays(n - 2) + countWays(n - 3);
		}
	}
	
	public static void main(String[] args) {
		System.out.println(countWays(5));	// 13
		// 11111, 1112, 1121, 1211, 122, 131, 113, 23, 221, 2111, 212, 32, 311
	}
}

しかし,ここでの再帰は1つのヘッダ再帰であり,すなわち先に再帰してから遡る(コンパイラはこれを1つのループ構造に最適化できない),3つの再帰の結果を統合することでアルゴリズムの実行時間は指数関数的に増加する(漸近時間複雑度はO(3^N)).動的計画の考え方を利用して再帰を最適化することができ、そのコードは以下の通りである.

public class Test04 {

	public static int countWaysDP(int n) {
		int[] map = new int[n + 1];
		for (int i = 0; i < map.length; i++) {
			map[i] = -1;
		}
		return countWaysDP(n, map);
	}

	private static int countWaysDP(int n, int[] map) {
		if (n < 0) {
			return 0;
		}
		else if (n == 0) {
			return 1;
		}
		else if (map[n] > -1) {
			return map[n];
		}
		else {
			map[n] = countWaysDP(n - 1, map) + countWaysDP(n - 2, map)
					+ countWaysDP(n - 3, map);
			return map[n];
		}
	}
	
	public static void main(String[] args) {
		System.out.println(countWaysDP(5));	// 13
		// 11111, 1112, 1121, 1211, 122, 131, 113, 23, 221, 2111, 212, 32, 311
	}

}