0


动态规划(Dynamic programming)详解

动态规划(Dynamic programming,简称DP)是一种将复杂问题分解成很多子问题,并将子问题的求解结果存储起来避免重复求解的一种算法。动态规划一般用来解决最优问题。而解决问题的过程,需要经历多个决策阶段。每个决策阶段都对应着一组状态。最后通过一组决策序列(动态转移方程),产生最终期望的最优解。

能用动态规划解决的问题,需要满足三个条件:最优子结构,无后效性和子问题重叠

一、基本概念(动态规划的三个特征

  1. 最优化原理(最优子结构性质):一个最优化策略具有这样的性质,不论过去状态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略。简而言之,一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。
  2. 无后效性:将各阶段按照一定的次序排列好之后,对于某个给定的阶段状态,它以前各阶段的状态无法直接影响它未来的决策,而只能通过当前的这个状态。换句话说,每个状态都是过去历史的一个完整总结。这就是无后向性,又称为无后效性。
  3. 子问题的重叠性:如果有大量的重叠子问题,我们可以用空间将这些子问题的解存储下来,避免重复求解相同的子问题,从而提升效率。本质上,动态规划是一种以空间换时间的技术。

上面是摘自百度百科的解释,比较拗口。下面看看网上摘的另一个回答。

一个模型指的是动态规划适合解决的问题模型。我把这个模型定义为“多阶段决策最优解模型”。

  1. 最优子结构:指的是,问题的最优解包含子问题的最优解。反过来说就是,我们可以通过子问题的最优解,推导出问题的最优解。如果我们把最优子结构,对应到我们前面定义的动态规划问题模型上,那我们也可以理解为,后面阶段的状态可以通过前面状态推导出来。
  2. 无后效性:无后效性,有两层含义,第一层含义是,在推导后面阶段状态的时候,我们只关心前面阶段的状态值,不关心这个状态是怎么一步步推导出来的。第二层含义是,某阶段状态一旦确定,就不受之后阶段的决策影响。即已经求解的子问题,不会再受到后续决策的影响。
  3. 重复子问题:不同的决策序列,到达某个相同的阶段时,可能会产生重复的状态。即存在子问题进行了重复计算。

举例:比如要求年级考试最高分时,我们可以把这个问题拆分成求每个班级的最高分,最后再通过每个班级的最高分去求年级的最高分。这个问题就符合最优子结构:可以从子问题的最优结果推出更大规模问题的最优结果。计算每个班的最优成绩就是子问题,你知道所有子问题的答案后,就可以借此推出全校学生的最优成绩这个规模更大的问题的答案。

再举个例子:假设学校有 10 个班,你已知每个班的最大分数差(最高分和最低分的差值),那么现在要计算全校学生中的最大分数差。此问题就不符合最优子结构,因为年级的最大分数差不能通过每个班级的最大分数差去计算出来(比如全校的最大分数差可能是 3 班的最高分和 6 班的最低分之差)。

对于这种最优子结构失效的情况,我们有时可以通过改造问题来使问题符合最优子结构

最大分数差,等价于什么?不就是等价于最高分数和最低分数的差么?不就是第一个例子中的求最值问题么?那么不就是具有最优子结构了么?此时就可以改变思路,借助最优子结构解决最值问题,再回过头解决最大分数差问题。

参考:什么是最优子结构、如何判定 DP 数组的遍历方向 - 知乎

同分治法(Divide and Conquer)一样,动态规划也是将子问题的求解结果进行合并,其主要用在当子问题需要一次又一次地重复求解时,将子问题的求解结果存储到一张表中(称为动态规划表)以免重复计算。因此当没有公共的(交叠的、重叠的)子问题时,动态规划算法并不适用,因为没有必要将一个不再需要的结果存储起来。例如,二分搜索(折半查找)就不具有重叠的子问题性质。

二、从斐波那契数列求解分析动态规划

斐波那契数列(Fibonacci sequence)指的是这样的一组数列:0、1、1、2、3、5、8、13……,即当前数为前两个数值相加,用数学公式表达为:F(0)=0,F(1)=1,F(n)=F(n - 1)+F(n - 2)(n ≥ 2,n ∈ N*)。

使用递归算法求解斐波那契数列:

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

如下图(n = 6 时的斐波那契数列计算过程的递归树形结构),我们为了计算F(6)的值,重复计算了许多遍的F(4)、F(3)……,(这就是重复子问题)这也导致递归算法的效率是十分低下的。

那么,我们是否能采用动态归纳来优化呢?

首先,需要分析“斐波那契数列”问题能否满足动态规划的使用条件。

  1. 最优子结构:F(n)的状态可以通过前面的状态推导出来。
  2. 无后效性:已经求解的子问题,不会再受到后续决策的影响。
  3. 重叠子问题:比如F(6)的求解,对于子问题F(4)进行了重复计算。

因此“斐波那契数列”问题可以使用动态规划去解决。那么具体应该怎么做呢?

基本思路

动态规划本质上是利用历史记录,来避免我们的重复计算。 而这些历史记录(动态规划表,我们需要一些变量来保存,一般是用一维数组或者二维数组来保存下面我们来看看动态规划的基本思路。

  1. 确定状态:将原问题划分为若干阶段,每个阶段对应若干个子问题,提取这些子问题的特征(称之为状态);并且一般是从最后一步从底层一步一步往上逆推的。
  2. 确定状态转移方程:寻找每一个状态的可能决策,或者说是各状态间的相互转移方式(用数学的语言描述就是 状态转移方程)。
  3. 确定开始以及边界条件。
  4. 按顺序求解每一个阶段的问题。

以“斐波那契数列”问题为例:

  1. 确定状态:所谓的状态其实就是问题的数学描述。比如定义F(n)表示第n个斐波那契数列的值。

  2. 确定状态转移方程式:假如我们不知道斐波那契数列的定义,就只有给定的一组数列(0、1、1、2、3、5、8、13……),我们一般通过观察归纳去总结每个状态之间的关系式。此时,F(n)=F(n-1)+F(n-2) 就是我们归纳出来的状态转移方程,F(n-1)和F(n-2) 就称为F(n)的最优子结构。

  3. 确定开始以及边界条件:当有了状态转移方程式后,我们还需要明确初始值。此时,F(0)=0,F(1)=1就是边界条件。

更多可以参考:30分钟弄懂动态规划算法详细讲解(超详细) - it610.com

当以上思路理清后,我们就可以写代码了。

    public static int fib2(int n) {
        if(n <= 1)
            return n;
        // 先创建一个数组来保存历史数据
        int[] dp = new int[n+1];
        // 给出初始值
        dp[0] = 0;
        dp[1] = 1;
        // 通过关系式来计算出 dp[n]
        for(int i = 2; i <= n; i++){
            dp[i] = dp[i-1] + dp[i-2];
        }
        // 把最终结果返回
        return dp[n];
    }

递归的时间复杂度是O(2^n),而动态规划由于将重复子问题的结果存起来了,因此时间复杂度仅为O(n)。

三、另一个例子

一个机器人位于一个m × n的网格中,机器人每次只能向右或者向下走一步,求机器人达到右下角总共有多少种方式?

  1. 确定状态:由于题目要求机器人从左上角到右下角有多少种方式,那么我们就定义dp[i][j]为:当机器人从左上角走到(i, j) 这个位置时,一共有 dp[i] [j] 种路径。那么,dp[m-1][n-1]就是机器人走到右下角的所有方式(注意:数组下标从0开始)

  2. 确定状态转移方程:想象以下,机器人要怎么样才能到达 (i, j) 这个位置?由于机器人只能向下走或者向右走,所以有两种方式到达:一种是从 (i-1, j) 这个位置向下走一步到达;另一种是从(i, j - 1) 这个位置向右走一步到达。因为是计算所有可能的步骤,所以是把所有可能走的路径都加起来,所以关系式是 dp[i] [j] = dp[i-1] [j] + dp[i] [j-1]。

  3. 确定开始以及边界条件:当机器人处在[0][0]这个位置时,dp[0][0]为0,因为不需要走。当机器人处在边界处,即i=0或者j=0时,此时机器人只可能有一种方式,即一直向下走(j=0)或者一直向右走(i=0)

因此,动态规划代码如下:

    public static int uniquePaths(int m, int n) {
        if(m<=0 || n<=0)
            return 0;
        // 先创建一个数组来保存历史数据
        int[][] dp = new int[m][n];
        // 给出初始值
        dp[0][0] = 0;
        for(int i = 0; i < m; i++){
            dp[i][0] = 1;
        }
        for(int i = 0; i < n; i++){
            dp[0][i] = 1;
        }
        // 通过关系式来计算出 dp[m][n]
        for(int i = 1; i < m; i++) {
            for(int j = 1; j < n; j++) {
                dp[i][j] = dp[i][j-1] + dp[i-1][j];
            }
        }
        return dp[m-1][n-1];
    }

四、参考文档

大厂面试常被问到的动态规划-技术圈

动态规划基础 - OI Wiki

什么是动态规划(Dynamic Programming)?动态规划的意义是什么? - 知乎

标签: 动态规划 算法

本文转载自: https://blog.csdn.net/qq_37771475/article/details/126855564
版权归原作者 Gent_倪 所有, 如有侵权,请联系我们删除。

“动态规划(Dynamic programming)详解”的评论:

还没有评论