LeetCode算法题-Climbing|LeetCode算法题-Climbing Stairs（Java实现）
这是悦乐书的第159次更新，第161篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第18题（顺位题号是70）。你正在爬楼梯，它需要n步才能达到顶峰。每次你可以爬1或2步，你可以通过多少不同的方式登顶？注意：给定n是一个正整数。例如：
输入：2说明：有两种方法可以爬到顶端
输出：2
1、1步 + 1步
2、2步
输入：3说明：有三种方法可以爬到顶端
输出：3
1、1步 + 1步 + 1步
2、1步 + 2步
3、2步 + 1步
输入：4说明：有5种方法可以爬到顶端
输出：5
1、1步 + 1步 + 1步 + 1步
2、1步 + 1步 + 2步
3、1步 + 2步 + 1步
4、2步 + 1步 + 1步
5、2步 + 2步
本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。
02 第一种解法
关于题目，可以从简单的条件开始推导。
当n等于1的时候，有1种方式。
当n等于2的时候，有2种方式。
当n等于3的时候，有3种方式。
当n等于4的时候，有5种方式。
【LeetCode算法题-Climbing|LeetCode算法题-Climbing Stairs（Java实现）】当n等于5的时候，有8种方式。
看到这，你会发现从n等于2开始，后一项等于前两项的和，这时很容易想到递归，于是就有了第一种解法。
public int climbStairs(int n) {
if (n == 1) {
return 1;
}
if (n == 2) {
return 2;
}
return climbStairs(n-1) + climbStairs(n-2);
}
03 第二种解法
上面的解法，你应该也发现问题了，运行太慢了。有什么可以优化的呢？既然只是求前两个数的和，那么可以引用数组来存值，而不是每次都来重新算一次。
public int climbStairs2(int n) {
int[] arr = new int[n+1];
return climb(n, arr);
}public int climb(int n, int[] arr){
if (n == 0 || n == 1) {
return 1;
} else if(arr[n] > 0) {
return arr[n];
}
arr[n] = climb(n-1, arr) + climb(n-2, arr);
return arr[n];
}
在climb方法里判断里，是要加上else if那个判断的，目的是避免重复计算，不判断的话就和第一种差不多了。
04 第三种解法
既然利用数组来存值，那么是不是可以省掉递归？直接拿数组元素返回结果就行。
public int climbStairs3(int n) {
int[] arr = new int[n+1];
arr[0] = 1;
arr[1] = 1;
for (int i=2;
i05 三种解法对比
为了验证哪种解法花费的时间更少，编写了一些简易的测试代码。
public static void main(String[] args) {
Easy_070_ClimbingStairs instance = new Easy_070_ClimbingStairs();
int arg = 44;
long start = System.nanoTime();
int result = instance.climbStairs(arg);
long end = System.nanoTime();
System.out.println("climbStairs---输入："+arg+" , 输出："+result+" , 用时："+(end-start)/1000+"微秒");
System.out.println("----------------------------");
long start2 = System.nanoTime();
int result2 = instance.climbStairs2(arg);
long end2 = System.nanoTime();
System.out.println("climbStairs2---输入："+arg+" , 输出："+result2+" , 用时："+(end2-start2)/1000+"微秒");
System.out.println("----------------------------");
long start3 = System.nanoTime();
int result3 = instance.climbStairs3(arg);
long end3 = System.nanoTime();
System.out.println("climbStairs3---输入："+arg+" , 输出："+result3+" , 用时："+(end3-start3)/1000+"微秒");
}
下面是运行的结果
climbStairs---输入：44 , 输出：1134903170 , 用时：2795896微秒
----------------------------
climbStairs2---输入：44 , 输出：1134903170 , 用时：9微秒
----------------------------
climbStairs3---输入：44 , 输出：1134903170 , 用时：6微秒
可以看出来，第三种解法是最优的，递归是好算法，但是会造成很多重复计算，影响速度，需要分场景来使用递归算法。
06 小结
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！
推荐阅读
- parallels|parallels desktop 解决网络初始化失败问题
- jhipster|jhipster 升级无效问题
- “精神病患者”的角度问题
- 画解算法（1.|画解算法：1. 两数之和）
- 【生信技能树】R语言练习题|【生信技能树】R语言练习题 - 中级
- Guava|Guava RateLimiter与限流算法
- 解决SpringBoot引用别的模块无法注入的问题
- 【Leetcode/Python】001-Two|【Leetcode/Python】001-Two Sum
- leetcode|leetcode 92. 反转链表 II
- 迷茫是人生常态