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

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

数据

结构

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

一、前言

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

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

二、动态规划

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

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

1. 基本思想

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

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

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

2. 问题分析

‍

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

（一） 问题引入

宝石挑选：

小 Q 是一个宝石爱好者。一天，小 Q 来到了宝石店，店家觉得小 Q 是个宝石行家，于是决定和小 Q 玩一个游戏。游戏规则如下：共有

块宝石，每块宝石在小 Q 心中都有其对应的价值。注意，由于某些宝石质量不佳，因此存在只有店家倒贴钱，小 Q 才愿意带走的宝石的情形，即宝石价值可以为负数。

小 Q 可以免费带走一个连续区间中的所有宝石，比如区间

或区间

中的所有宝石。请问小 Q 能带走的最大宝石价值是多少？

问题分析：

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

暴力求解

首先，我们枚举所有区间，暴力累加区间中所有宝石的价值，最后选一个价值最大的区间。时间复杂度

。

显然有些无法接受，因此想想有没有办法优化，比如优化掉暴力累加的那一部分。

优化 1.0

仔细思考不难发现，我们可以枚举区间右端点，然后固定右端点，左端点不断向左移动，边移动，边累加，就可以将时间复杂度优化到

。

例如，固定右端点为 3，那么左端点就从 3 移动到 1，边移动边累加结果，就可以在移动过程中计算出区间

、

、

的答案了。因此，枚举所有区间右端点，即可在

时间复杂度内找到答案。但是

时间复杂度还是有些过高，因此思考有没有办法继续优化呢？

优化 2.0

观察

的解法，不难发现，我们用了

的时间复杂度才求出了固定某个点为区间右端点时，区间最大价值和。

例如，我们固定了

为区间右端点后，通过从n到1枚举左端点，才求出了以

为区间右端点时的区间最大价值和，即

的时间复杂度。

那么，继续思考，「以

为区间右端点的区间最大和」，与「以

为区间右端点的区间最大和」，这两者之间是否有联系呢？

为了描述方便，接下来用

来代替「以

为区间右端点的区间最大和」，用

来代替第

块宝石的价值。

观察后不难发现，如果

为正数，则

一定等于

；如果

为负数，则

一定等于

。因此可以推导出如下转移方程：

根据上述转移方程，可以在

时间复杂度内求出最大的

，于是将此题时间复杂度优化到了

，而这个优化的过程就是「动态规划」的过程。

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

1. 将整个问题划分为一个个的子问题，并令

   

   为第

   

   个子问题的答案

2. 思考大规模的子问题如何从小规模的子问题推导而来，即如何由

   

   推出

   

这两个步骤便是「动态规划」解题思路的核心所在，即确定动态规划时的「状态」与「转移方程」。

（二） 动态规划概述

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

1. 动态规划解题思路

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

DP 状态

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

1. 最优子结构

2. 无后效性

最优子结构

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

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

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

例如在「宝石挑选」例题中，原有问题是「最大连续区间和」，子问题是「以

为右端点的连续区间和」。并且「以

为右端点的最大连续区间和」由「以

为右端点的最大连续区间和」推出，此时后者即为更小规模的子问题，因此满足「最优子结构」原则。

由此我们才定义 DP 状态

表示子问题的最优值，即「以

为右端点的最大连续区间和」。

无后效性

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

仍以「宝石挑选」例题为例，我们令 DP 状态

表示「以

为右端点的最大连续区间和」，我们只关心「以

为右端点的区间」这个子问题的最优值，并不关心这个子问题的最优值是从哪个其它子问题转移而来。

即无论

所表示区间的左端点是什么，都不会影响后续

的取值。影响

取值的只有

的数值大小。

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

我们对「宝石挑选」例题增加一个限制，即小 Q 只能挑选长度的连续区间。此时若我们定义

表示「以

为右端点的长度

的最大连续区间和」，则

的取值不仅取决于

的数值，还取决于

是如何得到的。

因为如果

取得最优值时区间长度

，则

不能从

转移得到，即

的状态定义有后效性。

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

DP 转移方程

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

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

在我们定义「DP 状态」

之后，我们考虑状态

如何从

这些更小规模的状态转移而来。

仔细思考可以发现，由于

表示的是连续区间的和，因此其取值只与

有关，与

均无关。

我们再进一步思考，

取值只有两种情况，一是向左延伸，包含

，二是不向左延伸，仅包含

，由此我们可以得到下述「DP 转移方程」：

注意，

且

。

2. 动态规划问题类别

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

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

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

（三） 习题实战

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