动态规划：是什么，如何工作以及学习资源
动态规划是由数学家和经济学家Richard Bellman开发的概念。
当时，Bellman正在寻找一种解决复杂优化问题的方法。优化问题要求您从一组选项中选择最佳解决方案。
一个优化问题的例子是旅行推销员问题。目标是找到最短的路径，以使推销员能够每个城市只访问一次并返回起始城市。
Bellman解决这些问题的方法是将它们分解为较小的子问题，并从最小到最大解决这些子问题。然后，他将子问题的结果存储起来，并重用它们来解决更大的子问题。这就是动态规划的主要思想。
什么是动态规划？
动态规划通过将优化问题分解为较小的子问题来解决它们，解决每个子问题一次，并存储它们的解决方案，以便可以重用和组合以解决更大的问题。问题从小到大解决，允许解决方案被重用。
动态规划的工作原理是什么？
使用动态规划解决问题涉及以下步骤：
- 定义子问题：将一个大问题分解为小的子问题。
- 解决子问题：这涉及解决已识别的子问题，可以使用递归或迭代来完成。
- 存储解决方案：将子问题的解决方案存储起来，以便可以重用。
- 构建原始问题的解决方案：从已经计算出的子问题中构建大问题的解决方案。
为了看到它的实际效果，我们使用这个过程计算第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
当我们解决每个子问题时，我们将解决方案存储在一个数组或表中，以便可以在解决更大的子问题时重用，如下所示：
| n | F(n) |
|---|---|
| 0 | 0 |
| 1 | 1 |
| 2 | 1 |
| 3 | 2 |
| 4 | 3 |
| 5 | 5 |
| 6 | 8 |
一旦所有子问题都被解决，我们就使用这些解决方案来构建原始问题的解决方案。
在这种情况下，原始问题的解决方案是第6个斐波那契数，它通过将F(5)和F(4)的结果相加得出，这些子问题是从最大问题中识别出来的。结果给出了8。
动态规划在哪里和为什么被使用？
动态规划用于需要将问题分解为较小子问题并使用它们的解决方案来解决更大问题的领域。
这些领域包括计算机科学、经济学、数学和工程学。在计算机科学中，它用于解决涉及序列、图形和整数值的问题，以及竞技编程。
在经济学中，它用于解决金融、生产和资源分配的优化问题。在数学中，动态规划用于博弈论、统计学和概率论中，它用于解决优化问题。
在工程学中，它用于解决资源分配、调度、制造、通信和控制系统等问题。
使用动态规划解决优化问题有以下几个优点：
- 效率：动态规划可以比其他优化算法更高效，因为它避免了多次重新计算相似问题。
- 解决大问题：动态规划非常适合解决使用其他方法无法解决的大规模优化问题。这是因为它将问题分解为较小的问题，减少了问题的复杂性。
- 最优解：如果子问题和目标被正确定义，动态规划算法可以找到问题的最优解。
- 简单：动态规划算法易于实现和理解，特别是如果问题可以按照特定顺序定义。
- 可扩展：通过添加附加的子问题和修改问题的目标，动态规划算法可以轻松扩展以解决更复杂的问题。
在解决优化问题时，动态规划是一个非常有用的工具，可以保证解决方案的效率。
动态规划中使用的方法
在动态规划中，有两种方法用于解决优化问题。它们是自顶向下方法和自底向上方法。
自顶向下方法
这种方法也被称为记忆化。记忆化是一种优化技术，主要用于通过将函数调用的结果存储在缓存中，并在下次需要时返回缓存的结果来使计算机程序更快。
自顶向下方法涉及递归和缓存。递归将一个函数用较简单的问题的版本作为参数调用自身。递归用于将问题分解为较小的子问题并解决这些子问题。
一旦解决了一个子问题，其结果被缓存并在出现类似问题时重复使用。自顶向下方法易于理解和实现，并且只解决一个子问题一次。然而，它的一个缺点是由于递归而占用大量内存。这可能导致堆栈溢出错误。
自底向上方法
自底向上方法，也称为填表法，通过迭代取代了递归，从而避免了堆栈溢出错误。
在这种方法中，将一个大问题分解为较小的子问题，并使用子问题的解来解决更大的问题。
首先从最大的子问题开始解决较小的子问题，将它们的结果存储在矩阵、数组或表中，因此得名填表法。
存储的结果解决了依赖于子问题的较大问题。然后通过使用先前计算的值解决最大的子问题，找到原始问题的结果。
这种方法通过消除递归来节省内存和时间，具有内存和时间效率高的优点。
可以通过动态规划解决的问题示例
以下是一些可以使用动态规划解决的编程问题：
#1. 背包问题
背包是一种由帆布、尼龙或皮革制成的袋子，通常绑在背部，士兵和徒步旅行者用来携带物品。
在背包问题中，你会面对一个背包，并给出其承载能力，你需要选择物品，每个物品都有其价值。你的选择应该是使得你所选物品的总价值最大化且物品的重量小于等于背包的容量。
以下是背包问题的一个例子：
假设你要去徒步旅行，背包的容量为15公斤。你有一张物品清单，列出了可以带上的物品以及它们的价值和重量，如下表所示：
| 物品 | 价值 | 重量 |
|---|---|---|
| 帐篷 | 200 | 3 |
| 睡袋 | 150 | 2 |
| 炉子 | 50 | 1 |
| 食物 | 100 | 2 |
| 水瓶 | 10 | 0.5 |
| 急救包 | 25 | 1 |
选择物品的一个子集，使得物品的总价值最大化，同时物品的总重量小于等于15公斤。
背包问题的实际应用包括选择证券以加入投资组合以最小化风险并最大化利润，以及找到最不浪费的原材料切割方式。
#2. 调度问题
调度问题是一个优化问题，目标是将任务最优地分配给一组资源。这些资源可以是机器、人员或其他用于完成任务的资源。
以下是调度问题的一个例子：
假设你是一个负责安排一组任务的项目经理，这些任务需要由一组员工完成。每个任务都有一个开始时间、结束时间和一个能够完成任务的员工列表。
下表描述了任务及其特性：
| 任务 | 开始时间 | 结束时间 | 合格的员工 |
|---|---|---|---|
| T1 | 9 | 11 | A, B, C |
| T2 | 10 | 12 | A, C |
| T3 | 11 | 13 | B, C |
| T4 | 12 | 14 | A, B |
将每个任务分配给一个员工，以最小化总完成时间。
调度问题可能出现在制造业中，当试图优化资源（如机器、材料、工具和劳动力）的分配时。
在医疗保健领域中，也可能遇到调度问题，以优化床位、人员和医疗用品的使用。该问题还可能出现在供应链管理和教育领域。
#3. 旅行商问题
这是一个应用最广泛的优化问题之一，可以使用动态规划来解决。
旅行商问题提供了一个城市列表以及每对城市之间的距离。你需要找到最短的可能路线，使得每个城市都恰好访问一次，并返回起点城市。
以下是旅行商问题的一个例子：
假设你是一个销售员，需要以最短的时间访问一组城市。你有一个需要访问的城市列表以及每对城市之间的距离，如下表所示：
| 城市 | A | B | C | D | E |
|---|---|---|---|---|---|
| A | 0 | 10 | 15 | 20 | 30 |
| B | 10 | 0 | 35 | 25 | 15 |
| C | 15 | 35 | 0 | 30 | 20 |
| D | 20 | 25 | 30 | 0 | 10 |
| E | 30 | 15 | 20 | 10 | 0 |
在休闲行业中，当尝试为旅游者规划路线时，可以遇到旅行售货员问题；在物流中，当规划货物运输时可以遇到旅行售货员问题；在交通运输中，当规划公交车线路时可以遇到旅行售货员问题；还有在销售行业等等。
显然，动态规划有许多实际应用，这有助于更多地了解它。
考虑以下资源以深入了解动态规划。
资源
Richard Bellman的动态规划
动态规划是一本由Richard Bellman编写的书，他提出了动态规划并在其早期阶段进行了发展。
| 预览 | 产品 | 评分 | 价格 | |
|---|---|---|---|---|
 |
Dynamic Programming (Dover Books on Computer Science) | $16.99 | Buy on Amazon |
这本书以易于理解的方式编写，只需要基本的数学和微积分知识即可理解其中的内容。在这本书中，Bellman介绍了多阶段决策过程的数学理论，这是动态规划的关键。
然后，该书还研究了多阶段生产过程中的瓶颈问题、存在性和唯一性定理以及最优库存方程。
这本书最好的地方在于Bellman提供了许多复杂问题的例子，涉及物流、调度理论、通信理论、数学经济学和控制过程等领域，并展示了动态规划如何解决这些问题。
这本书有Kindle、精装和平装版本可供选择。
动态规划算法大师课程
这个 Dynamic Programming Algorithms Master Course by Udemy 由Google的软件工程师Apaar Kamal和与Google合作的Prateek Narang提供。
该课程经过优化，旨在帮助学习者在编程竞赛中取得卓越成绩，其中涉及许多需要动态规划的问题。
除了编程竞赛选手，该课程还适合希望提高对算法理解的程序员和准备编程面试和在线编码轮次的人。
该课程长度超过40小时，深入讲解了动态规划。课程首先提供对递归和回溯等概念的复习。
然后，它涵盖了博弈论、字符串、树和图、矩阵乘法、位掩码、组合数学和子序列、划分问题以及多维动态规划等概念。
竞技编程基础，掌握算法
Udemy提供了由Prateek Narang和Amal Kamaar开设的课程，涵盖了动态规划、数学、数论以及对竞技编程有用且相关的高级数据结构和算法。
在深入研究更复杂的算法和技术之前，该课程对数据结构和算法进行了复习，这对竞技编程非常有帮助。
该课程涵盖了动态规划、数学、博弈论、模式匹配、位掩码以及在编程竞赛中使用和测试的众多高级算法。
Udemy课程分为10个模块和42个章节，在每个章节之后提供大量的练习题。这门畅销课程对于任何对竞技编程感兴趣的人来说都是必备的。
最后的话
动态规划是任何程序员学习以改善解决实际问题的有益技能。因此，程序员应该考虑通过参考推荐的资源来掌握这个重要的工具。
