跳台阶问题的优化跳台阶的算法优化

92 阅读 0 评论 61 点赞

我是靠谱客的博主野性毛巾，这篇文章主要介绍跳台阶问题的优化跳台阶的算法优化，现在分享给大家，希望可以做个参考。

跳台阶的算法优化

原因：因为普通的递归会有很多重复的，比如F(4)=f(3)+f(2),f(3)=f(2)+f(1),这里f(2)就重复了；

优化思路，就是把已经算的了放进map中，然后需要的时候取出来

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 private static int getWays(int n){
HashMap<Integer, Integer> m = new HashMap<>();
if (n<=0){
return 0;
}
if (n==1) return
1;
if (n==2) return 2;
if (m.containsKey(n)){
return m.get(n);
}else {
int value = getWays(n-1)+getWays(n-2);
m.put(n,value);
return value;
}