减少重复搜索,递归思路,拆分大问题,转换成小问题

代码如下

    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);
    }
最后修改:2021 年 02 月 14 日
如果觉得我的文章对你有用,请随意赞赏