首页 / 算法 / LeetCode算法题目之70.爬楼梯
LeetCode算法题目之70.爬楼梯
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了LeetCode算法题目之70.爬楼梯,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2475字,纯文字阅读大概需要4分钟。
内容图文
![LeetCode算法题目之70.爬楼梯](/upload/InfoBanner/zyjiaocheng/601/586ce6bac46344d28385f232d97e4e0c.jpg)
LeetCode算法题目之70.爬楼梯
题目描述:
假设你正在爬楼梯。需要 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 阶
解答:
一:递归方式
public static void main(String[] args) {
// int n = 1;
// int n = 4;
// int n = 5;
int n = 45;
System.out.println(climbStairs1(n));
// System.out.println(climbStairs2_temp(n));
// System.out.println(climbStairs3(n));
}
// 普通递归方式,时间复杂度2的N次方,空间复杂度N
// n=45时,超时间限制
public static int climbStairs1(int n) {
/**
* 由示例可知,n=1则1种(1),n=2则2种(1+1,2),n=3时3种(1+1+1,1+2;2+1),n=4时5种(2阶时+2;3阶时+1)即(2种+3种),n=5为n=4的种类数加n=3的种类数
* 即有爬楼梯方法种数f(n) = f(n-1)+f(n-2),n>=3
*/
if(n==1){
return 1;
} else if(n==2){
return 2;
} else {
return climbStairs1(n-1) + climbStairs1(n-2);
}
}
二:记忆递归方式
public static void main(String[] args) {
// int n = 1;
// int n = 4;
// int n = 5;
int n = 45;
// System.out.println(climbStairs1(n));
System.out.println(climbStairs2_temp(n));
// System.out.println(climbStairs3(n));
}
// 记忆递归方式,时间复杂度N,空间复杂度N
// n=44时,超时间限制
public static int climbStairs2_temp(int n) {
int[] temp = new int[n+1];
return climbStairs2(n,temp);
}
public static int climbStairs2(int n, int[] temp) {
/**
* 有爬楼梯方法种数f(n) = f(n-1)+f(n-2),n>=3
* f(1)=1; f(2)=2
* 若n=45,则将44时和43时种类数存入数组temp,同理42~3的所有种类数亦被存储,故递归上跳时无需重复计算
*/
if (temp[n]>0){ // 若计算过n的种类数,则无需计算
return temp[n];
}
if(n==1){
return 1;
} else if(n==2){
return 2;
} else {
return climbStairs2(n-1,temp) + climbStairs2(n-2,temp);
}
}
三:动态规划方式
public static void main(String[] args) {
// int n = 1;
// int n = 4;
// int n = 5;
int n = 45;
// System.out.println(climbStairs1(n));
// System.out.println(climbStairs2_temp(n));
System.out.println(climbStairs3(n));
}
// 动态规划方式,时间复杂度N,空间复杂度1
public static int climbStairs3(int n) {
/**
* 1;2; (1+2)3; (2+3)5; (3+5)8; (5+8)13
* 定义 left right add
*/
int left=0;
int right=0;
int add=1;
for(int i=1; i<=n; i++){
right = left; // 0; 1; 1; 2
left = add; // 1; 1; 2; 3
add = right+left; /// 1; 2; 3; 5
}
return add;
}
内容总结
以上是互联网集市为您收集整理的LeetCode算法题目之70.爬楼梯全部内容,希望文章能够帮你解决LeetCode算法题目之70.爬楼梯所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。