动态规划：它是什么、它是如何工作的以及学习资源

动态规划是由数学家和经济学家理查德贝尔曼提出的概念。

当时，贝尔曼正在寻找解决复杂优化问题的方法。 优化问题要求您从一组选项中选择最佳解决方案。

优化问题的一个例子是旅行商问题。 目标是找到最短路线，让推销员恰好访问每个城市一次并返回出发城市。

贝尔曼解决这些问题的方法是将它们分解成更小的子问题，并从小到大解决子问题。 然后他存储子问题的结果，并重新使用它们来解决更大的子问题。 这是动态规划背后的主要思想。

什么是动态规划？

动态规划通过将优化问题分解为更小的子问题来解决优化问题，对每个子问题求解一次，并存储它们的解，以便它们可以被重用和组合以解决更大的问题。 问题从小到大解决，允许重复使用解决方案。

动态规划是如何工作的？

使用动态规划解决问题涉及以下步骤：

1. 定义子问题：一个大问题被分成小的子问题。
2. 解决子问题：这涉及解决已识别的子问题，这可以使用递归或迭代来完成。
3. 存储解决方案：存储子问题的解决方案，以便可以重复使用。
4. 构建原始问题的解决方案：大问题的解决方案是从已经计算好的子问题中构建的。

为了解实际效果，我们使用此过程计算第 6 个斐波那契数 F(6)。

首先，定义需要解决的子问题。

F(n) = F(n-1) + F(n-2) 对于 n > 1

因此：F(6) = F(5) + F(4)

F(5) = F(4) + F(3)

F(4) = F(3) + F(2)

F(3) = F(2) + F(1)

F(2) = F(1) + F(0)

F(1) = 1

F(0) = 0

第二步涉及使用递归函数或迭代过程解决每个子问题。 我们从最小到最大解决子问题，重用较小子问题的结果。 这给了我们以下信息：

F(0) = 0

F(1) = 1

F(2) = F(1) + F(0) = 1 + 0 = 1

F(3) = F(2) + F(1) = 1 + 1 = 2

F(4) = F(3) + F(2) = 2 + 1 = 3

F(5) = F(4) + F(3) = 3 + 2 = 5

F(6) = F(5) + F(4) = 5 + 3 = 8

当我们解决每个子问题时，我们将解决方案存储在数组或表中，以便它们可以在解决更大的子问题时重复使用，如下所示：

一旦解决了所有子问题，我们就使用这些解决方案来构建原始问题的解决方案。

在这种情况下，原始问题的解决方案是第 6 个斐波那契数，它是通过对 F(5) 和 F(4) 的结果求和而找到的，这些子问题是从最大问题中识别出来的。 结果给了我们 8。

在哪里以及为什么使用动态规划？

动态规划用于我们遇到的问题可以分解为更小的子问题的领域，它们的解决方案用于解决更大的问题。

这些领域包括计算机科学、经济学、数学和工程学。 在计算机科学中，它用于解决涉及序列、图形和整数值的问题以及竞争性编程。

在经济学中，它用于解决金融、生产和资源配置中的优化问题。 在数学中，动态规划用于博弈论、统计学和概率论，用于解决优化问题。

在工程中，它用于解决资源分配、调度、制造、通信和控制系统中的问题。

使用动态规划解决优化问题有几个优点：

1. 效率：动态规划比其他优化算法更高效，因为它避免了多次重新计算类似问题。
2. 解决大问题：动态规划非常适合解决使用其他方法无法解决的大型优化问题。 这是因为它将问题分解为更小的问题，降低了它们的复杂性。
3. 最优解：如果子问题和目标定义正确，动态规划算法可以找到问题的最优解。
4. 简单性：动态规划算法易于实现和理解，尤其是当问题可以按特定顺序定义时。
5. 可扩展性：通过添加额外的子问题和修改问题的目标，可以轻松扩展动态规划算法以解决更复杂的问题。

在解决优化问题时，动态规划是确保解决方案效率的非常有用的工具。

动态规划中使用的方法

在动态规划中，有两种方法用于解决优化问题。 这些是自上而下的方法和自下而上的方法。

自上而下的方法

这种方法也称为记忆化。 记忆化是一种优化技术，主要用于通过将函数调用的结果存储在缓存中并在下次需要时返回缓存的结果而不是再次计算它们来使计算机程序更快。

自上而下的方法涉及递归和缓存。 递归涉及一个函数以问题的更简单版本作为参数调用自身。 递归用于将问题分解为更小的子问题并解决子问题。

一旦解决了一个子问题，它的结果就会被缓存起来，并在类似问题出现时重新使用。 自上而下易于理解和实施，并且只解决一个子问题一次。 然而，它的一个缺点是它会因为递归而占用大量内存。 这可能导致堆栈溢出错误。

自下而上的方法

自下而上的方法，也称为制表法，取消了递归，代之以迭代，从而避免了堆栈溢出错误。

在这种方法中，一个大问题被分解成更小的子问题，然后使用子问题的解决方案来解决更大的问题。

较小的子问题首先从大到小求解，其结果存储在矩阵、数组或表中，因此得名制表。

存储的结果解决了依赖于子问题的更大问题。 然后通过使用先前计算的值解决最大的子问题来找到原始问题的结果。

这种方法的优点是通过消除递归来提高内存和时间效率。

动态规划可以解决的问题的例子

以下是一些可以使用动态规划解决的编程问题：

#1。 背包问题

背包是由帆布、尼龙或皮革制成的包，通常背在背上，供士兵和徒步旅行者用来携带补给品。

在背包问题中，系统会向您展示一个背包，鉴于它的承载能力，您需要选择物品，每件物品都有其价值。 您的选择应该使您获得最大的物品总价值，并且物品的重量小于或等于背包容量。

背包问题的一个例子如下：

想象一下，您正在徒步旅行，并且有一个容量为 15 公斤的背包。 您有一份可以随身携带的物品清单，以及它们的价值和重量，如下表所示：

选择要携带的物品的子集，使物品的总价值最大化，同时总重量小于或等于背包容量，即 15 公斤。

背包问题的实际应用涉及选择证券以添加到投资组合中以最小化风险和最大化利润，以及找到减少原材料浪费最少的方法。

#2。 调度问题

调度问题是一个优化问题，其目标是将任务最优地分配给一组资源。 资源可以是用于完成任务的机器、人员或其他资源。

下面给出了一个调度问题的例子：

假设您是一名项目经理，负责安排一组需要由一组员工完成的任务。 每个任务都有一个开始时间、一个结束时间，以及一个有资格完成它的员工列表。

下表描述了任务及其特征：

将每项任务分配给一名员工，以最大限度地减少总完成时间。

在试图优化机器、材料、工具和劳动力等资源的分配时，制造业可能会遇到调度问题。

在优化床位、人员和医疗用品的使用时，它也可能在医疗保健中遇到。 其他可能出现此问题的行业是项目管理、供应链管理和教育。

#3。 旅行商问题

这是研究最多的优化问题之一，可以使用动态规划来解决。

旅行商问题提供了一个城市列表和每对城市之间的距离。 您需要找到访问每个城市恰好一次并返回起点城市的最短路线。

下面给出了旅行商问题的示例：

想象一下，您是一名销售人员，需要在尽可能短的时间内访问一组城市。 你有一个你需要访问的城市列表以及每对城市之间的距离，如下表所示：

旅行商问题可能在休闲行业试图为游客规划路线时遇到，物流在规划货物运输时遇到，交通运输在规划公交线路时遇到，在销售行业等等。

显然，动态规划在现实世界中有很多应用，这有助于进一步了解它。

考虑以下资源来阐述您的动态规划知识。

资源

Richard Bellman 的动态规划

Dynamic Programming 是 Richard Bellman 的一本书，他提出了动态规划并在其早期阶段进行了开发。

预习	产品	评分	价格
	动态规划（多佛计算机科学书籍）	暂无评分	17.29 美元	在亚马逊上购买

本书以通俗易懂的方式编写，只需要数学和微积分的基本知识即可理解文本。 在书中，贝尔曼介绍了多阶段决策过程的数学理论，这是动态规划的关键。

然后，本书研究了多阶段生产过程中的瓶颈问题、存在唯一性定理以及最优库存方程。

这本书最棒的地方在于，贝尔曼提供了物流、调度理论、通信理论、数理经济学和控制过程等领域的许多复杂问题的例子，并展示了动态规划如何解决这些问题。

这本书有 Kindle、精装和平装版。

动态规划算法硕士课程

Udemy 的动态编程算法硕士课程由 Google 的软件工程师 Apaar Kamal 和也曾在 Google 工作的 Prateek Narang 提供。

该课程经过优化，可帮助学习者在编程竞赛中脱颖而出，该竞赛具有许多需要动态编程的问题。

除了编程竞赛者之外，该课程非常适合希望提高对算法的理解的程序员以及准备编程面试和在线编码轮次的人员。

该课程时长超过 40 小时，深入介绍了动态规划。 该课程首先提供递归和回溯等概念的复习。

然后涵盖博弈论中的动态规划、字符串、树和图、矩阵求幂、位掩码、组合学和子序列、划分问题和多维动态规划，以及许多其他概念。

竞争性编程基础，精通算法

Udemy 提供了由 Prateek Narang 和 Amal Kamaar 编写的竞争性编程基础课程，该课程以对竞争性程序员有用且相关的方式涵盖动态编程、数学、数论以及高级数据结构和算法。

在深入研究在竞争性编程中派上用场的更复杂的算法和技术之前，该课程提供了对数据结构和算法的复习。

该课程涵盖动态规划、数学、博弈论、模式匹配、位掩码以及在编程竞赛中使用和测试的无数高级算法。

Udemy 课程分为 10 个模块和 42 个部分，并在每个部分后提供大量练习题。 对于任何对竞争性编程感兴趣的人来说，这本畅销书课程都是必备的。

最后的话

动态编程对于任何程序员来说都是一项有益的技能，可以通过学习提高他们对现实世界问题的解决能力。 因此，程序员应该考虑通过建议的资源将这个重要工具添加到他们的工具箱中。

接下来，您可以查看用于数据科学的编程语言。