一、题目描述与分析
不难看出,这是一道常见的递归算法题型。
f(n)={
1 n=1;
2 n=2;
f(n-1)+f(n-2) n>2;
}
二、解题代码及算法描述
推出公式后,首先想到的是普通递归思路解题。
class Solution {
public int climbStairs(int n) {
if(n==1) return 1;
if(n==2) return 2;
return climbStairs(n-1)+climbStairs(n-2);
}
}
}
提交结果:
但这样会超出时间限制,时间复杂度太高Of(n*n),这里我们以n==5为例说明原因
由图可看出,在递归的过程中求f(3),f(2),f(1)时会重复的进行求解,所以时间复杂度会非常高。导致超时。
解决方法1:
我们可以把已经求过的值放到hashmap中,这样用的时候找有没有对应n的值,如果有就直接用,没有就进行计算后保存到hashmap中。算法时间复杂度为O(n)。
class Solution {
private Map<Integer,Integer> storeMap=new HashMap<>();
public int climbStairs(int n) {
if(n==1) return 1;
if(n==2) return 2;
if(storeMap.get(n)!=null){
return storeMap.get(n);
}else{
int result=climbStairs(n-1)+climbStairs(n-2);
//把结果存入HashMap中
storeMap.put(n,result);
return result;
}
}
}
提交结果:
超越100%用户。
解决方法2:
我们可以用循环解决问题。正向思维想算法。f1表示f(n-1),f2表示f(n-2)的值,从3开始。f(3)=f1+f2;到f(4)时,f1=f(3)的值,f2=f1的值。以此类推写算法。时间复杂度也是O(n).
class Solution {
public int climbStairs(int n) {
//通过,超过100%用户
if(n==1) return 1;
if(n==2) return 2;
int f1=2,f2=1,sum=0;
for(int i=3; i<=n;i++){
sum=f1+f2;
f2=f1;
f1=sum;
}
return sum;
}
}
提交结果:
超越100%用户。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
文章由极客之音整理,本文链接:https://www.bmabk.com/index.php/post/114655.html