面试编程题拾遗（04） --- 上楼梯有多少种方式

傷城~ 2021-09-22 03:28 239阅读 0赞

题目：一个小孩上一个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
    	}
    }

然而，这里的递归是一个头递归，也就是说要先递归再回溯（编译器无法将其优化为一个循环结构），而且是将三个递归的结果进行合并，这样的话算法的运行时间呈指数增长（渐近时间复杂度为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
    	}
    
    }