动态规划、回溯、贪心，分治顶

算法之名

发布于 2020-03-19 10:22:59

5390

动态规划篇

从斐波那契数列开始

我们先给出斐波那契数列的常用算法类

public class Fibonacci {
    private static int num = 0;
    private Fibonacci() {
    }
    public static int fib(int n) {
        num++;
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        return fib(n - 1) + fib(n - 2);
    }

    public static void main(String[] args) {
        num = 0;
        int n = 20;
        long start = System.nanoTime();
        int res = Fibonacci.fib(n);
        long end = System.nanoTime();
        System.out.println(res);
        System.out.println((end - start) / 1000000000.0);
        System.out.println(num);
    }
}

运行结果

6765 3.96599E-4 21891

此时我们调大n的值为40

运行结果

102334155 0.473162902 331160281

再调大n的值为42

267914296 1.302307318 866988873

我们可以看到此处随着n的增大，时间是几何倍数增长，由此我们可知斐波那契数列的时间复杂度为O(2^n)

但我们发现斐波那契数列的存在着大量的重复计算，如下图所示，我们来看计算一个n=5的时候都有哪些重复计算的地方

在这里我们可以看到3被计算了2次。

而2则被计算了3次，这还是n = 5的情况下，如果随着n值的增大，重复计算的次数就会越来越多。

所以我们给出了一个新的记录重复计算值不需要重新计算的斐波那契算法类

public class Fibonacci {
    private static int num = 0;
    private static List<Integer> memo = new ArrayList<>();
    private Fibonacci() {
    }
    //记忆化搜索
    public static int fib(int n) {
        num++;
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        if (memo.get(n) == -1) {
            memo.set(n,fib(n - 1) + fib(n - 2));
        }
        return memo.get(n);
    }

    public static void main(String[] args) {
        num = 0;
        int n = 42;
        for (int i = 0;i <= n;i++) {
            memo.add(-1);
        }
        long start = System.nanoTime();
        int res = Fibonacci.fib(n);
        long end = System.nanoTime();
        System.out.println(res);
        System.out.println((end - start) / 1000000000.0);
        System.out.println(num);
    }
}

这次我们再来计算n = 42，运行结果

267914296 4.2859E-5 83

由结果可知，当我们减少了计算次数，斐波那契算法的时间复杂度从O(2^n)一下子降到了O(n)级别，这就相当于我们在列表中命中了缓存，无需866988873次计算，而计算次数只降低到了83次。

很明显递归的求解是一种自上而下的思考方式，那我们可不可以换一种思考的方式，使用自下而上的方式来求解呢

public class Fibonacci {
    private static List<Integer> memo = new ArrayList<>();
    private Fibonacci() {
    }
    //动态规划
    public static int fib(int n) {
        memo.add(0);
        memo.add(1);
        for (int i = 2;i <= n;i++) {
            memo.add(memo.get(i - 1) + memo.get(i - 2));
        }
        return memo.get(n);
    }

    public static void main(String[] args) {
        int n = 42;
        long start = System.nanoTime();
        int res = Fibonacci.fib(n);
        long end = System.nanoTime();
        System.out.println(res);
        System.out.println((end - start) / 1000000000.0);
    }
}

运行结果

267914296 4.456E-5

而这样的一种自下而上的计算方式，我们就称之为动态规划。将原问题拆解成若干子问题，同时保存子问题的答案，使得每个子问题只求解一次，最终获得原问题的答案。总体的思路如下图

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度