减少重复搜索,递归思路,拆分大问题,转换成小问题
代码如下
public static void main(String[] args) {
/*
普通斐波那契数列结果:1134903170
普通斐波那契用时:0
记忆化斐波那契数列结果:1134903170
记忆化斐波那契用时:2852
*/
//普通斐波那契用时
long start1 = System.currentTimeMillis();
System.out.println("普通斐波那契数列结果:"+memoryFib(new HashMap<>(), 45));
System.out.println("普通斐波那契用时:" + (System.currentTimeMillis() - start1));
//记忆化斐波那契用时
start1 = System.currentTimeMillis();
System.out.println("记忆化斐波那契数列结果:"+getFib(45));
System.out.println("记忆化斐波那契用时:" + (System.currentTimeMillis() - start1));
}
//普通斐波那契
public static Integer getFib(int n) {
if (n == 1 || n == 2) return 1;
return getFib(n - 1) + getFib(n - 2);
}
//记忆化斐波那契数列
public static Integer memoryFib(HashMap<Integer, Integer> hashMap, int n) {
//递归基线条件
if (n == 1 || n == 2) return 1;
//判断字典中是否有该数据
if (hashMap.containsKey(n)) {
return hashMap.get(n);
} else {
//如果没有,计算向下递归
hashMap.put(n, memoryFib(hashMap, n - 1) + memoryFib(hashMap, n - 2));
}
return hashMap.get(n);
}
此处评论已关闭