最近遇到一个类似爬楼梯的算法题。索性对递归的处理总结一下。
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?注意:给定 n 是一个正整数。示例 1:输入:2
输出:2
解释:有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶示例 2:输入:3
输出:3
解释:有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
int climbStairs(int n) {
if(n == 1) return 1;
else if(n == 2) return 2;
else return climbStairs(n-1) + climbStairs(n-2);
}
Map<Integer,Integer> map = new HashMap();
public int climbStairs(int n) {
if(n==1) return 1;
else if(n == 2) return 2;
else if(map.containsKey(n)) return map.get(n);
else {
int result = climbStairs(n-1) + climbStairs(n-2);
map.put(n,result);
return result;
}
}
public int climbStairs(int n) {
if(n == 1) return 1;
if(n == 2) return 2;
int pre2 = 1;
int pre1 = 2;
int result =0;
for(int i=3;i<=n;i++){
result = pre1+pre2;
pre2 = pre1;
pre1 = result;
}
return result;
}
如上,这道题目的解法主要还是应用了递归的编程技巧。递归,去的过程称为“递”,回来的过程称为“归”。一般所有的递归问题都可以用递归公式来解决。写出递归公式,问题就解决了一多半。
f(n) = f(n-1)+1 其中 f(1)=1
在jvm中,“栈”又称“堆栈”。每个方法在执行的过程中都会创建一个栈帧用于存储局部变量表、操作数栈、动态链接、方法出口等信息。每一个方法从调用直至执行完成的过程,就对应着一个栈帧在虚拟机栈中入栈到出栈的过程。如果递归深度多大,导致栈不够用,就会导致 StackOverflowError。如解法1,当n足够大,就会导致这个问题。
如何尽量避免?
解法1在实际应用中很容易超时,因为时间复杂度太高。那么怎么计算递归算法的时间复杂度呢?其实在所有的递归问题中,因为是大问题拆分小问题的思路,所以整个计算过程算下来就好像是一棵树。
假定加法时间复杂度忽略为1,那么第一层做加法1次,为1;第二次做2次,为2,第三层做4次为4...。这棵树最高为n,最低为n/2;当高为n时,所有层加和为2n-1,当高为n/2时,所有层加和为2n/2-1,无论如何,它的时间复杂度为指数级的,当n足够大时,是很恐怖的。这就是利用递归树求解递归的时间复杂度。
以上。。。
王争 《数据结构和算法之美》