外国手表网站,搜狐做网站,上海市企业服务云官网,notepad wordpressjava面试题#xff0c;上楼梯有多少种方式
题目#xff1a;一个小孩上一个N级台阶的楼梯#xff0c;他可以一次走1阶、2阶或3阶#xff0c;那么走完N阶有多少种方式。
很自然的想法是使用递归#xff1a;
public class Test04 {
public static int countWays(int n) {…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
}
}
