算法系列-动态规划(1):初识动态规划

2020-12-01

昨天,罗拉去面试回来,垂头丧气。显然是面试不顺利,我赶忙过去安慰。

经过询问才知道,罗拉面试挂在了动态规划。

说到动态规划,八哥可就来精神了,于是就结合劳拉的面试题简单的和她介绍了动态规划。

事情是这样的,劳拉的面试官给了她一道题,题目如下:

有一个数列,规律如下:1、1、2、3、5、8、13....
如果要求第N个数值,用代码如何实现。

罗拉一看这题,心里一喜,“这题目,不简单吗?”。

于是和面试官卖弄道:“这不是斐波那契数列吗?这个数列从第3项开始,每一项都等于前两项之和”。

面试官笑笑,“没错,那么如何实现求第n个数呢?”

“这简单,稍后”,罗拉毫不含糊,在纸上啪啪写下几行代码,很快哈,两分钟不到,她就写出来了,只用了两行代码。

public class Fibonacci {
    public int rec_fib(int n) {
        if (n == 1 || n == 2) return 1;
        else return rec_fib(rec_fib(n - 1) + rec_fib(n - 2));
    }
}

八哥仔细一看,好家伙,年轻人不讲码德啊,直接递归。

在罗拉仔细准备迎接面试官得夸奖的时候。

面试官问:“递归,不错,还有更好的方法吗?”

罗拉懵了,她觉得自己的代码够简单,应该没啥问题吧。

仔细想了一会儿,也没想出其他的办法。最后只能和面试官互道珍重回家等通知了。


那么,大家发现这个写法的问题了吗?

下面八哥就和大家唠嗑唠嗑。

首先,写法肯定是没问题的,但是问题出在递归上面。

下面,我们分别计算一下n=10n=45 的时候,看看这个程序耗费的时间

public class Fibonacci {
    public static void main(String[] args) {
        long star = System.currentTimeMillis();
        System.out.println(rec_fib(10));
        long end = System.currentTimeMillis();
        System.out.println("计算n=10 耗时:"+(end - star)/1000 + "s");

        star = System.currentTimeMillis();
        System.out.println(rec_fib(45));
        end = System.currentTimeMillis();
        System.out.println("计算n=45 耗时:"+(end - star)/1000 + "s");
    }

    public static long rec_fib(int n) {
        if (n == 1 || n == 2) return 1;
        else return rec_fib(n - 1) + rec_fib(n - 2);
    }
}

输出结果如下:

55
计算n=10 耗时:0s
1134903170
计算n=45 耗时:3s

发现没?计算fn(45)的居然花了三秒多,如果我们计算100,1000那岂不是原地螺旋爆炸?

那为啥会计算fn(45)会花这么多时间呢?接下来我们就分析分析。

首先我们根据这个数列的特点,很容易写出下面的推导公式。

推导公式

然后,我们可以画一下递归图
递归图

发现问题没有?是不是发现有些数据被多次计算?比如f(48)被算了两次,f(47)会被算3次,越往下算的越多。
重复计算

仔细想想,按照这样重复计算,n = 50那得重复多少次啊。

我们再来分析一下罗拉写的这个算法的时间复杂度。

按照我们这么拆分下去,很容易发现,这玩意就基本等于一颗完全二叉树了。自然时间复杂度就是:

指数级别的时间复杂度,不爆炸都对不起递归了好吧。


出了问题,我们就要解决问题。

打蛇打七寸,既然知道痛点是重复计算,那我们从重复计算的地方着手就好了。

我们很容易想到把计算过的值存起来,用的时候直接用就好了。

比如我们可以用数据记录计算过的值。

罗拉听完,若有所思,随后啪啪一份代码就出来了。

public class Fibonacci {
    public static long men_fib(int n) {
        if (n < 0) return 0;
        if (n <= 2) return 1;
        long[] men = new long[n + 1];
        men[1] = 1;
        men[2] = 1;
        menHelper(men, n);
        return men[n];
    }

    public static long menHelper(long[] men, int n) {
        if (n == 1 || n == 2) return 1;
        if (men[n] != 0) return men[n];
        men[n] = menHelper(men, n - 1) + menHelper(men, n - 2);
        return men[n];
    }
}

使用一个men[n]数组记录计算过的值,这样避免了重复计算。

这个时候罗拉又重新执行f(10)和fn(45),查看执行时间.

public class Fibonacci {
    public static void main(String[] args) {
        long star = System.currentTimeMillis();
        System.out.println(men_fib(10));
        long end = System.currentTimeMillis();
        System.out.println("计算n=10 耗时:" + (end - star) / 1000 + "s");

        star = System.currentTimeMillis();
        System.out.println(men_fib(45));
        end = System.currentTimeMillis();
        System.out.println("计算n=45 耗时:" + (end - star) / 1000 + "s");
    }
    public static long men_fib(int n) {
        if (n < 0) return 0;
        if (n <= 2) return 1;
        long[] men = new long[n + 1];
        men[1] = 1;
        men[2] = 1;
        menHelper(men, n);
        return men[n];
    }

    public static long menHelper(long[] men, int n) {
        if (n == 1 || n == 2) return 1;
        if (men[n] != 0) return men[n];
        men[n] = menHelper(men, n - 1) + menHelper(men, n - 2);
        return men[n];
    }
}

执行结果

55
计算n=10 耗时:0s
1134903170
计算n=45 耗时:0s

看,基本都是瞬间执行完。

即使计算f(100),也很快。

3736710778780434371
计算n=100 耗时:0s

效率提升可观吧,如果罗拉当时这么做了,至少还能再蹭一杯茶。然后再相忘江湖吧。

我们使用一个数据记录计算过的值,相当于整了一个备忘录,这是递归常见的优化方式。这个其实已经有了一点动态规划的味道。

不过呢,这个带备忘录的递归属于自顶向下的方法。那怎么理解自顶向下呢?废话不多说,上图

自顶向下

看这个图,我们执行的时候是按照这个顺序f(50),f(49)...f(1),f(1)执行的吧,从上往下计算,可以粗略的认为这就是自顶向下。

我们还可以采用自底向上的方式,也就是按照下面的形式
自底向上

我们还是用一个数组dp记录计算过值,因为我们已经知道了,第1个和第2个数。所以我们可以通过第1个和第2个数。从1开始,递推出50,这个就是自底向上。

按照这个思路,罗拉很快,一分钟不到哈,就写出了代码,年轻人就是雷厉风行。

    public static long fib(int n) {
        if (n == 1 || n == 2) return 1;
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 1;
        for (int i = 3; i <= n; i++)
            dp[i] = dp[i - 1] + dp[i - 1];
        return dp[n];
    }

同样执行了执行f(10)和fn(45)

public class Fibonacci {
    public static void main(String[] args) {
        long star = System.currentTimeMillis();
        System.out.println(fib(10));
        long end = System.currentTimeMillis();
        System.out.println("计算n=10 耗时:" + (end - star) / 1000 + "s");

        star = System.currentTimeMillis();
        System.out.println(fib(45));
        end = System.currentTimeMillis();
        System.out.println("计算n=100 耗时:" + (end - star) / 1000 + "s");
    }

    public static long fib(int n) {
        if (n == 1 || n == 2) return 1;
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 1;
        for (int i = 3; i <= n; i++)
            dp[i] = dp[i - 1] + dp[i - 1];
        return dp[n];
    }

}

查看执行时间。

55
计算n=10 耗时:0s
1134903170
计算n=45 耗时:0s

答案显而易见,效果与备忘录一样,这个时候我们再分析一下时间复杂度。

这种自底向上方式就是动态规划。(ps:自顶向上不等于动态规划)

整个过程,我们就用了一个额外数组dp,和一个for循环,那么很容易得到时间复杂度为

这对指数级别的时间复杂度,在N比较大的情况下,就是降维打击啊。

可能有人有疑问了,我如果对递归用了备忘录优化,不是可以达到一样的效果吗?这样的话动态规划有什么优势呢?

年轻人别急嘛,动态规划没那么简单,当然掌握核心思想也不难。

我这只是举个例子,其实斐波那契数列没必要用动态规划,只是这个例子比较简单而已,刚好可以用来入门。

动态规划也不是用于解决这类问题的。

动态规划通常用来求解最优化问题,一般此类问题有很多的解,我们希望找到一个最优的解(比如最大值、最小值)

注意我说的是我们找的解是一个最优解,而不是最优解,因为一个问题可能有多个解都是最优解。

是不是有点难以理解?那我举个例子:

比如,我有100米的钢材,可以切成不同的长度出售,不同长度价格不同。
就像图中划分那样,如果我们要赚最多钱,怎么卖比较好呢?

这个时候你用备忘录就很难做了吧。

怎样,没头绪了吧,别急用动态规划就很容易做这类题目,至于怎么做,且听下回分解。

欢迎关注八哥:兔八哥杂谈,会持续更新一些文章。

此文为原创文章,转自啊请注明出处!!!