vlambda博客
学习文章列表

数据结构【1】-如何理解数据结构中的动态规划【上】?



点击蓝字
关注我们



AI研习图书馆,发现不一样的精彩世界


数据
结构


动态规划知识点详解及实践

一、前言

算法与数据结构,是研发类或技术类岗位求职过程中无法避免的一座大山,无论是在笔试还是面试中。经常在网上看到,诸如不懂算法与数据结构,就不懂真正的编程的一类话语。笔试时,熟悉数据结构常用算法,可以让我们高效解决编程题目;面试时,熟悉数据结构,会让我们对于面试官的提问对答如流。面试官几乎必问:你主要使用什么语言?那你了解数据结构吗?那我问你几个基本的问题......

先天不足,后天努力;学海无涯,天道出勤。由于最近在突击算法与数据结构,故本专栏系列主要记录算法与数据结构系列知识点,欢迎点赞、打卡学习~
二、动态规划

算法与数据结构中,动态规划问题一直是大厂面试时最频繁出现的算法题,其主要原因在于此类问题灵活度高,思维难度大,没有很明显的套路做法。

正是因为这个原因,我将持续更新此系列,来尝试破解面试中所涉及的动态规划问题。本次更新是这个系列的第一篇总结,主要目的是说明动态规划是什么,常见动态规划问题我们应该如何思考?

1. 基本思想

动态规划,通常用于求解具有某种最优性质的问题。在这类问题中,可能会有许多可行解。每一个解都对应于一个值,我们希望找到具有最优值的解。

动态规划方法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的。

若用分治法来解这类问题,则分解得到的子问题数目太多,有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,这样就可以避免大量的重复计算,节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到,只要它被计算过,就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样,但它们具有相同的填表格式。

2. 问题分析

本篇总结一共分成三个部分,具体内容框架如下图所示:

数据结构【1】-如何理解数据结构中的动态规划【上】?

(一) 问题引入

宝石挑选:

小 Q 是一个宝石爱好者。一天,小 Q 来到了宝石店,店家觉得小 Q 是个宝石行家,于是决定和小 Q 玩一个游戏。游戏规则如下:共有 数据结构【1】-如何理解数据结构中的动态规划【上】? 块宝石,每块宝石在小 Q 心中都有其对应的价值。注意,由于某些宝石质量不佳,因此存在只有店家倒贴钱,小 Q 才愿意带走的宝石的情形,即宝石价值可以为负数。

小 Q 可以免费带走一个连续区间中的所有宝石,比如区间 数据结构【1】-如何理解数据结构中的动态规划【上】? 或区间  数据结构【1】-如何理解数据结构中的动态规划【上】? 中的所有宝石。请问小 Q 能带走的最大宝石价值是多少?

问题分析:

首先思考最暴力最直接的解法。

暴力求解

首先,我们枚举所有区间,暴力累加区间中所有宝石的价值,最后选一个价值最大的区间。时间复杂度 数据结构【1】-如何理解数据结构中的动态规划【上】?数据结构【1】-如何理解数据结构中的动态规划【上】? 显然有些无法接受,因此想想有没有办法优化,比如优化掉暴力累加的那一部分。

优化 1.0

仔细思考不难发现,我们可以枚举区间右端点,然后固定右端点,左端点不断向左移动,边移动,边累加,就可以将时间复杂度优化到 数据结构【1】-如何理解数据结构中的动态规划【上】?

例如,固定右端点为 3,那么左端点就从 3 移动到 1,边移动边累加结果,就可以在移动过程中计算出区间 数据结构【1】-如何理解数据结构中的动态规划【上】? 数据结构【1】-如何理解数据结构中的动态规划【上】? 数据结构【1】-如何理解数据结构中的动态规划【上】? 的答案了。因此,枚举所有区间右端点,即可在 数据结构【1】-如何理解数据结构中的动态规划【上】? 时间复杂度内找到答案。 但是 数据结构【1】-如何理解数据结构中的动态规划【上】? 时间复杂度还是有些过高,因此思考有没有办法继续优化呢?

优化 2.0

观察 数据结构【1】-如何理解数据结构中的动态规划【上】? 的解法,不难发现,我们用了 数据结构【1】-如何理解数据结构中的动态规划【上】? 的时间复杂度才求出了固定某个点为区间右端点时,区间最大价值和。
例如,我们固定了 数据结构【1】-如何理解数据结构中的动态规划【上】? 为区间右端点后,通过从n 到1 枚举左端点,才求出了以 数据结构【1】-如何理解数据结构中的动态规划【上】? 为区间右端点时的区间最大价值和,即 数据结构【1】-如何理解数据结构中的动态规划【上】? 的时间复杂度。
那么,继续思考,「以 数据结构【1】-如何理解数据结构中的动态规划【上】? 为区间右端点的区间最大和」,与「以 数据结构【1】-如何理解数据结构中的动态规划【上】? 为区间右端点的区间最大和」,这两者之间是否有联系呢?
为了描述方便,接下来用 数据结构【1】-如何理解数据结构中的动态规划【上】? 来代替「以 数据结构【1】-如何理解数据结构中的动态规划【上】? 为区间右端点的区间最大和」,用 数据结构【1】-如何理解数据结构中的动态规划【上】? 来代替第 数据结构【1】-如何理解数据结构中的动态规划【上】? 块宝石的价值。
观察后不难发现,如果 数据结构【1】-如何理解数据结构中的动态规划【上】? 为正数,则 数据结构【1】-如何理解数据结构中的动态规划【上】? 一定等于 数据结构【1】-如何理解数据结构中的动态规划【上】? ;如果 数据结构【1】-如何理解数据结构中的动态规划【上】? 为负数,则 数据结构【1】-如何理解数据结构中的动态规划【上】? 一定等于 数据结构【1】-如何理解数据结构中的动态规划【上】? 。因此可以推导出如下转移方程:

数据结构【1】-如何理解数据结构中的动态规划【上】?

根据上述转移方程,可以在 数据结构【1】-如何理解数据结构中的动态规划【上】? 时间复杂度内求出最大的 数据结构【1】-如何理解数据结构中的动态规划【上】? ,于是将此题时间复杂度优化到了 数据结构【1】-如何理解数据结构中的动态规划【上】? ,而这个优化的过程就是「动态规划」的过程。

总结:在上述推导的过程中,一共可以分为两步:

  1. 将整个问题划分为一个个的子问题,并令 数据结构【1】-如何理解数据结构中的动态规划【上】? 为第 数据结构【1】-如何理解数据结构中的动态规划【上】? 个子问题的答案
  2. 思考大规模的子问题如何从小规模的子问题推导而来,即如何由 数据结构【1】-如何理解数据结构中的动态规划【上】? 推出 数据结构【1】-如何理解数据结构中的动态规划【上】?
这两个步骤便是「动态规划」解题思路的核心所在,即确定动态规划时的 「状态」与「转移方程」

(二) 动态规划概述

动态规划(Dynamic Programming),因此常用 DP 指代动态规划。本块内容我们主要讲解「 动态规划解题思路 」与「 动态规划问题类别 」。

1. 动态规划解题思路

动态规划主要分为两个核心部分,一是确定「DP 状态」,二是确定「DP 转移方程」。

DP 状态

「DP 状态」的确定主要有两大原则:

  1. 最优子结构

  2. 无后效性

最优子结构

以「宝石挑选」为例题来讲解这两大原则,首先是「最优子结构」。

什么是「最优子结构」?将原有问题化分为一个个子问题,即为子结构。而对于每一个子问题,其最优值均由「更小规模的子问题的最优值」推导而来,即为最优子结构。

因此「DP 状态」设置之前,需要将原有问题划分为一个个子问题,且需要确保子问题的最优值由「更小规模子问题的最优值」推出,此时子问题的最优值即为「DP 状态」的定义。

例如在「宝石挑选」例题中,原有问题是「最大连续区间和」,子问题是「以 数据结构【1】-如何理解数据结构中的动态规划【上】? 为右端点的连续区间和」。并且「以 数据结构【1】-如何理解数据结构中的动态规划【上】? 为右端点的最大连续区间和」由「以 数据结构【1】-如何理解数据结构中的动态规划【上】? 为右端点的最大连续区间和」推出,此时后者即为更小规模的子问题,因此满足「最优子结构」原则。

由此我们才定义 DP 状态 数据结构【1】-如何理解数据结构中的动态规划【上】? 表示子问题的最优值,即「以 数据结构【1】-如何理解数据结构中的动态规划【上】? 为右端点的最大连续区间和」。

无后效性

而对于「无后效性」,顾名思义,就是我们只关心子问题的最优值,不关心子问题的最优值是怎么得到的。

仍以「宝石挑选」例题为例,我们令 DP 状态 数据结构【1】-如何理解数据结构中的动态规划【上】? 表示「以 数据结构【1】-如何理解数据结构中的动态规划【上】? 为右端点的最大连续区间和」,我们只关心「以 数据结构【1】-如何理解数据结构中的动态规划【上】? 为右端点的区间」这个子问题的最优值,并不关心这个子问题的最优值是从哪个其它子问题转移而来。

即无论 数据结构【1】-如何理解数据结构中的动态规划【上】? 所表示区间的左端点是什么,都不会影响后续 数据结构【1】-如何理解数据结构中的动态规划【上】? 的取值。影响 数据结构【1】-如何理解数据结构中的动态规划【上】? 取值的只有 数据结构【1】-如何理解数据结构中的动态规划【上】? 的数值大小。

那怎样的状态定义算「有后效性」呢?

我们对「宝石挑选」例题增加一个限制,即小 Q 只能挑选长度的连续区间。此时若我们定义 数据结构【1】-如何理解数据结构中的动态规划【上】? 表示「以 数据结构【1】-如何理解数据结构中的动态规划【上】? 为右端点的长度  数据结构【1】-如何理解数据结构中的动态规划【上】? 的最大连续区间和」,则  数据结构【1】-如何理解数据结构中的动态规划【上】? 的取值不仅取决于 数据结构【1】-如何理解数据结构中的动态规划【上】? 的数值,还取决于 数据结构【1】-如何理解数据结构中的动态规划【上】? 是如何得到的。

因为如果 数据结构【1】-如何理解数据结构中的动态规划【上】? 取得最优值时区间长度  数据结构【1】-如何理解数据结构中的动态规划【上】? ,则 数据结构【1】-如何理解数据结构中的动态规划【上】? 不能从 数据结构【1】-如何理解数据结构中的动态规划【上】? 转移得到,即 数据结构【1】-如何理解数据结构中的动态规划【上】? 的状态定义有后效性。

最后概括一下,「最优子结构」就是「DP 状态最优值由更小规模的 DP 状态最优值推出」,此处 DP 状态即为子问题。而「无后效性」就是「无论 DP 状态是如何得到的,都不会影响后续 DP 状态的取值」。

DP 转移方程

有了「DP 状态」之后,我们只需要用「分类讨论」的思想来枚举所有小状态向大状态转移的可能性即可推出「DP 转移方程」。

我们继续以「宝石挑选」问题为例。

在我们定义「DP 状态」 数据结构【1】-如何理解数据结构中的动态规划【上】? 之后,我们考虑状态 数据结构【1】-如何理解数据结构中的动态规划【上】? 如何从 数据结构【1】-如何理解数据结构中的动态规划【上】? 这些更小规模的状态转移而来。

仔细思考可以发现,由于 数据结构【1】-如何理解数据结构中的动态规划【上】? 表示的是连续区间的和,因此其取值只与 数据结构【1】-如何理解数据结构中的动态规划【上】? 有关,与 数据结构【1】-如何理解数据结构中的动态规划【上】? 均无关。

我们再进一步思考, 数据结构【1】-如何理解数据结构中的动态规划【上】? 取值只有两种情况,一是向左延伸,包含 数据结构【1】-如何理解数据结构中的动态规划【上】?,二是不向左延伸,仅包含 数据结构【1】-如何理解数据结构中的动态规划【上】? ,由此我们可以得到下述「DP 转移方程」:

数据结构【1】-如何理解数据结构中的动态规划【上】?
注意, 数据结构【1】-如何理解数据结构中的动态规划【上】? 数据结构【1】-如何理解数据结构中的动态规划【上】?

2. 动态规划问题类别

讲述完 DP 问题的解题思路后,我们来大致列举一下 DP 问题的类别。

DP 问题主要分为两大类,第一大类是 DP 类型,第二大类是 DP 优化方法。

数据结构【1】-如何理解数据结构中的动态规划【上】?

如上图所示,其中在 DP 类型部分,一般面试过程中最常考察的就是「线性 DP」,而在优化方法部分,最常见的是「RMQ 优化」,即使用线段树或其它数据结构查询区间最小值,来优化 DP 的转移过程。

(三) 习题实战

由于篇幅限制,习题实战部分请看下一期文章,谢谢~

算法与数据结构知识点总结第一篇,更多精彩,敬请期待~

推荐阅读文章

[1] 
[2] 
[3] 
[4] 
[5] 
[6] 

[7] 

[8] 

[9] 

[10] 

[11] 

[12] 

[13] 

[14] 

[15] 

[16] 

[17] 

[18] 

[19] 

[20] 

   ......


数据结构【1】-如何理解数据结构中的动态规划【上】?


数据结构【1】-如何理解数据结构中的动态规划【上】?
点击"在看"了解更多精彩内容
数据结构【1】-如何理解数据结构中的动态规划【上】?


数据结构【1】-如何理解数据结构中的动态规划【上】?
转载是一种动力 分享是一种美德


数据结构【1】-如何理解数据结构中的动态规划【上】?
Bilibili : 洛必达数数
CSDN博客:算法之美DL
GitHub:statisticszhang



关注AI研习图书馆,发现不一样的精彩世界