java面试题，上楼梯有多少种方式

- 日理万妓 2023-09-23 16:55 24阅读 0赞

java面试题，上楼梯有多少种方式

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