• 周五. 8月 19th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

动态规划算法

admin

11月 28, 2021

Dynamic Programming 基本介绍

Dynamic Programming是五大常用算法策略之一,简称DP,译作中文是“动态规划”,可就是这个听起来高大上的翻译坑苦了无数人,因为看完这个算法你可能会觉得和动态规划根本没太大关系,它对“动态”和“规划”都没有太深的体现。

举个最简单的例子去先浅显的理解它,有个大概的雏形,找一个数组中的最大元素,如果只有一个元素,那就是它,再往数组里面加元素,递推关系就是,当你知道当前最大的元素,只需要拿当前最大元素和新加入的进行比较,较大的就是数组中最大的,这就是典型的DP策略,将小问题的解保存起来,解决大问题的时候就可以直接使用。

Fibonacci 斐波拉契数列动态规划实现

第一个数是1,第二个数也是1,从第三个数开始,后面每个数都等于前两个数之和。要求:输入一个n,输出第n个斐波那契数。

还是我们上节讨论递归与分治策略时候举的第一个例子——Fibonacci数列问题,它实在太经典了,所以将其反复拿出来说。

我们如果深入分析一下上节说过的递归方法解决Fibonacci数列,就会发现出现了很多重复运算,比如你在计算f(5)的时候,你要计算f(4)和f(3),计算f(4)又要计算(3)和f(2),计算f(3),又要计算f(2)和f(1),看下面这个图

对f(3)和f(2)进行了重复运算,这还是因为5比较小,如果要计算f(100),那你可能要等到天荒地老它还没执行完

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

上面就是递归的解法,代码看着很简单易懂,但是算法复杂度已经达到了O(2^n),指数级别的复杂度,再加上如果n较大会造成更大的栈内存开销,所以非常低效。

DP策略解决这个问题

我们知道导致这个算法低效的根本原因就是递归栈内存开销大,对越小的数要重复计算的次数越多,那既然我们已经将较小的数,诸如f(2),f(3)……这些计算过了,为什么还要重复计算呢,这时就用到了DP策略,将计算过的f(n)保存起来。我们看看代码:

   //使用数组记录前100个斐波那契数
    static int[] arr = new int[100];

    public static int fibonacci(int n) {
        if (n == 1) return 1;
        else if (n == 2) return 1;
        else {
            if (n <= 100 && arr[n] != 0) {
                return arr[n];
            } else {
                arr[n] = simFibonacci(n - 1) + simFibonacci(n - 2);
                return arr[n];
            }
        }
    }

arr数组初始化为0,arr[i]就表示f(i),每次先判断arr[i]是否为0,如果为0则表示未计算过,则递归计算,如果不为0,则表示已经计算过,那就直接返回。

这样的好处避免了很大程度上重复的计算,但是对栈内存的开销虽然有减小但还不是很显著,因为只要有递归,栈内存就免不了有较大开销。所以针对Fibonacci数列我们还有一个递推的方式来计算,其实这也符合DP策略的思想,都是将计算过的值保存起来。

动态规划解题步骤

1、确定状态
简单的说,就是解动态规划时需要开一个数组,数组的每个元素f[i]或者f[i][j]代表什么,类似解数学题中,xyz代表什么一样,具体分为下面两个步骤:
——-研究最优策略的最后一步
——-化为子问题
2、转移方程
根据子问题定义直接得到
3、初始条件和边界情况
初始条件一般都是a[0]、a[1]这种,多看看
边界条件主要是看数组的边界,数组越不越界
4、计算顺序
利用之前的计算结果

发表回复

您的电子邮箱地址不会被公开。