一直以来自己算法这一块都比较薄弱，所以还是在努力寻找时间，开始补充能量。接下来会在这里分享一下，我解题的过程和最终代码。
Leetcode原题
思路
看到题目可以一下子就知道这是一道递归题型。人每次有2种爬楼梯的方式，要么是一次走1阶梯，要么是一次走2阶梯。
爬1阶层的楼梯 只能走1阶，所以只有1种方法
爬2阶层楼梯，可以为 2种：
1阶+1 阶
2阶
爬3阶楼梯可以为:
1+1+1
1+2
2+1
所以是3种方法。
通过观察可以发现，爬n阶楼梯有多少种方法取决于，第一次是先走1阶后剩余n-1阶的走法数量。还是先2阶走后，剩余n-2阶的走法数量。所以归纳起来爬第n阶楼梯的方法数量，等于 2 部分之和
爬上 n-1 阶楼梯的方法数量。因为再爬1阶就能到第n阶
爬上 n−2 阶楼梯的方法数量，因为再爬2阶就能到第n阶。
fn=(fn-1)+ (fn-2)
妙啊！看到这一看就是老递归了。那我们就先以递归的写法试试
代码
/** * @author: youjp * @slogan: 天下风云出我辈，一入代码岁月催 * @create: 2022-04-16 21:35 * @description: * @Version: 1.0 */ public class Solution { public int climbStairs(int n) { if (n==1){ return 1; } if (n==2){ return 2; } else { return climbStairs(n-1)+climbStairs(n-2); } } public static void main(String[] args) { Solution solution=new Solution(); int sum =solution.climbStairs(5); System.out.println(sum); } }
这种写法看起来方便，但是时间复杂度为（O2）。
尝试提交一看，我靠，超时了。。。
那怎么办呢，我们再来分析一下，之前的逻辑，爬取2阶
f(2)=f(2-1）+f(0)=f(1)+f(0);
爬取3阶
f(3)=f(3-1)+f(3-2)=f(2)+f(1);
爬取4阶
f(4)=f(4-1)+f(4-2)=f(3)+f(2)
…
可以发现，爬几阶等于爬取前面的2阶的方法汇总。而我们之前的写法，其实有重复的部分，爬3阶的时候1阶的方法数量重复计算了，爬取4阶的时候，2阶的方法数量重复计算了。那么问题大概率是出在这。。。
妙啊，我感觉我又站起来了，嘿嘿嘿~
我们可以利用hashmap的特性和或者局部变量的方式来存储一下。之前已经有计算过的阶梯方法。
代码如下：
//利用hashmap，实现时间复杂度O(n) public class Solution { HashMap map =new HashMap(); public int climbStairs(int n) { if (n==1){ return 1; } if (n==2){ return 2; } if (null!= map.get(n)){ return (int) map.get(n); }else { int nums= climbStairs(n-1)+climbStairs(n-2); map.put(n,nums); return nums; } } }
方法2
//利用循环加递归，实现时间复杂度O(n) public class Solution { public int climbStairs(int n) { if (n==1){ return 1; } if (n==2){ return 2; } int pre=2; int prepre=1; int sum=0; for (int i=3;i<=n;i++){ sum= pre+prepre; prepre= pre; pre= sum; } return sum; } public static void main(String[] args) { Solution solution=new Solution(); int sum =solution.climbStairs(5); System.out.println(sum); } }
提交测试
oh,yeh 还是辣么滴丝滑 雀氏润~~~~
因为目前个人算法能力有限，有更好的方法的小伙伴可以在评论区留言分享，大家一起共同进步。
有兴趣的老爷，还可以关注我的公众号【一起收破烂】，回复【006】获取2022最新java面试资料以及简历模型120套哦~
