关于爬楼梯问题以及优化
日期： 2018-02-25 分类： 个人收藏 356次阅读
题目是这样的：
假设你正在爬楼梯，一共有N阶楼梯。但每次你只能爬一阶或者两阶，你能有多少种不同的方法爬到楼顶部？
初出茅庐，面试被问到，回家做个笔记记录一下。
最先想到的应该是用递归的方法解：
public static int climbStairs1(int n) {
int ways;
if(n==1||n==2) {
ways = n;
}else {
ways = climbStairs1(n-1)+climbStairs1(n-2);
}
return ways;
}
这样解表面固然没毛病，但是学习算法的时候应该听过递归的方法慎用，慎用，慎用！重要的事情说3遍...这个方法当N很大时，时间复杂度成指数型的增长，问题很大啊~
于是乎，面试官问道，你有什么优化的方法嘛？（我有好的方法，不就直接写出来了嘛？不过感觉面试官都喜欢由浅入深，(￣▽￣)"）
上网查询了一下，确实有一些不一样的方法：
public static int climbStairs2(int n) {
if(n==0)
return 1;
int[] arr = new int[n+1];
arr[0]=1;
arr[1]=1;
for(int i=2;i<=n;i++) {
arr[i] = arr[i-1]+arr[i-2];
}
return arr[n];
}
这个方法是利用动态规划来解决问题的，利用数组来存储有多少种方法（与第一种那个方法比，实际就是利用空间换取时间，即空间复杂度很大），当N很大的时候，仍会出现问题，不过对于面试来说的话应该足够了...
网上有种斐波那契数列的通项公式，有大神还能想得起来，做得出来，也是很强
public static int climbStairs4(int n) {
if (n == 0)
return 1;
if (n == 1 || n == 2)
return n;
int result = (int) Math.floor(
1 / Math.sqrt(5) * (Math.pow((1 + Math.sqrt(5)) / 2, n + 1) - Math.pow((1 - Math.sqrt(5)) / 2, n + 1)));
return result;
}
除特别声明，本站所有文章均为原创，如需转载请以超级链接形式注明出处：SmartCat's Blog
标签：算法
精华推荐