重叠子问题

动态规划是一种强大的算法技术，用于通过将优化问题分解为更简单的子问题并系统地存储这些子问题的解决方案来避免重复计算来解决它们。当一个问题可以被分解为重叠的子问题时，它特别有效，可以重用中间结果以获得显著的效率提升。

动态规划的核心思想是从下往上解决问题，从最小的子问题开始，逐步构建更大、更复杂实例的解决方案。这种方法与分治策略形成对比，后者倾向于通过将问题分解为不重叠的子问题来解决问题。

动态规划的定义特征之一是记忆化（memoization）的概念，它涉及存储昂贵函数调用的结果，并在再次出现相同输入时重用这些结果。这大大减少了重复计算的数量，并显著提高了算法效率。

动态规划适用于广泛的问题，包括组合优化、序列比对、最短路径查找和资源分配等。经典示例包括斐波那契数的计算、使用 Dijkstra 等算法查找图中的最短路径以及背包问题。

动态规划有两种主要方法：自顶向下和自底向上。在自顶向下方法（也称为记忆化）中，问题被递归地分解为更小的子问题，并将这些子问题的解决方案存储以供以后使用。在自底向上方法中，问题从最简单的子问题开始，通过迭代方式解决，直到原始问题。

尽管动态规划可以提高效率，但它并不总是解决所有问题的最佳选择。当子问题重叠且可以独立求解时，它最有效，并且对于没有重叠子问题或内存需求显著更高的问题，它可能不是最优的。

总之，动态规划是算法设计和优化领域中的宝贵工具。它使我们能够通过将复杂问题分解为易于管理的子问题来解决它们，利用记忆化避免重复计算，并通过高效的计算最终得出最优解决方案。其多功能性和广泛的应用性使其成为解决各种挑战性计算问题的基本技术。

重叠子问题

在算法问题解决领域，“重叠子问题”的概念是支撑各种优化技术（如动态规划）的基本原理。重叠子问题指的是在同一问题的大范围内的相同或相似的较小子实例的出现。这种现象通常出现在可以分解为更小、更易于管理的子问题的复杂问题中。

识别重叠子问题的意义在于其能够显着提高解决问题的效率。当一个大问题可以被细分为重叠的子问题时，就可以重用先前计算的解决方案。这种重用可以防止重复计算，并节省大量时间和资源，最终使算法运行得更快，消耗的计算资源更少。

处理重叠子问题的关键在于高效地存储和检索这些子问题的解决方案。这个过程通常通过记忆化或制表来实现。记忆化涉及存储昂贵函数调用的结果，并在再次出现相同的输入时重用这些结果。另一方面，制表则涉及构造一个表或数组来系统地存储子问题的解决方案，其中每个单元格代表一个唯一的子问题实例。

重叠子问题在许多领域和问题类型中都很普遍。例如，在动态规划中，斐波那契数的计算或图中 द्या最短路径的计算等问题就表现出重叠子问题。同样，在背包问题等组合优化问题中，在考虑不同项目子集时出现的子问题通常是重叠的。

识别和利用重叠子问题是许多算法和问题解决范式的有效性的核心。通过将复杂问题分解为较小的重复组件，算法可以更有效地导航解决方案空间。这不仅加速了计算过程，还有助于开发更优雅、更精简的算法，这些算法能够更好地应对挑战性的计算问题。

理解重叠子问题

想象一下，您有一个需要解决的复杂问题，并且您意识到这个问题可以分解为更小的、相似的子问题。当独立求解这些子问题时，会得到一个有助于解决更大问题的解决方案。然而，当您开始解决主要问题时，您会注意到其中一些较小的子问题会重复出现多次。这种重复就是重叠子问题的概念所在。

计算斐波那契数列是一个经典的例子。斐波那契数列是一系列数字，其中每个数字是前两个数字之和。在数学上，它可以定义为

重叠子问题的示例

假设您想使用上述递归关系计算 F(5)。为此，您需要计算 F(4) 和 F(3)，它们都依赖于各自的子问题。计算 F(4) 需要计算 F(3) 和 F(2)，计算 F(3) 需要计算 F(2) 和 F(1)。

计算过程如下

在这个过程中，您可以观察到 F(2) 被计算了两次，一次在计算 F(4) 时，一次在计算 F(3) 时。同样，F(1) 和 F(0) 也在计算树的不同分支中被多次计算。这就是重叠子问题的本质——相同的子问题被反复解决。

使用动态规划进行优化

重叠子问题为使用动态规划技术进行优化提供了绝佳的机会。与其多次重新计算相同的子问题，不如将它们的解决方案存储在数组或哈希映射等数据结构中。这样，当您将来遇到相同的子问题时，就可以直接查找其解决方案，而无需进行重复计算。

在斐波那契示例中，通过一次性存储较小的斐波那契数的解决方案，可以显着减少所需的计算次数。一次计算 F(2) 并存储其结果，可以节省多次重新计算，如果您没有考虑到重叠子问题，这些重新计算本会发生。

记忆化

记忆化是一种强大的优化技术，用于通过减少重复计算来提高算法效率。它涉及存储昂贵函数调用的结果，并在再次出现相同的输入时返回缓存的结果。当一个函数多次使用相同的参数集调用时，就会出现重复计算，此时该技术特别有用。通过记忆化这些函数调用，程序员可以显着提高代码的性能。

在记忆化中，利用数组、哈希映射或缓存等数据结构来存储函数调用的计算结果。当使用特定的输入参数调用一个函数时，算法首先检查结果是否已存在于缓存中。如果存在，则直接返回存储的结果，而无需重新计算。如果找不到结果，函数将按正常方式计算结果，但在返回结果之前，会将结果缓存以供将来使用。

记忆化对于递归算法尤其有益，在这些算法中，函数为了解决问题而用修改后的输入调用自身。这些递归调用可能导致使用相同参数多次调用相同的函数。记忆化通过将结果存储在内存中，可以防止算法重新计算相同的结果，从而显着降低时间复杂度。

使用递归解决斐波那契数列是记忆化的一个生动例子。如果没有记忆化，计算较高的斐波那契数需要多次重新计算较小的斐波那契数，导致指数级时间复杂度。然而，通过记忆化先前计算的斐波那契数的结果，算法可以实现线性时间复杂度并显着提高其性能。

记忆化的应用

以下是记忆化方法的一些应用

• 斐波那契数列计算：斐波那契数列是记忆化可以非常有效的经典示例。使用递归方法计算斐波那契数可能导致对相同值的重复计算。记忆化有助于存储中间结果，避免了重新计算已计算值的需要，从而大大减少了计算时间。
• 组合问题：各种组合问题涉及探索所有可能的组合或排列，导致指数级时间复杂度。可以使用记忆化来存储子问题的解决方案，确保同一个子问题不会被多次解决，这是朴素递归方法中常见的问题。
• 图算法：Dijkstra 最短路径算法和 Floyd-Warshall 所有对最短路径算法等算法涉及对同一子路径的重复计算。记忆化可以通过缓存子路径计算的结果来优化这些算法，降低时间复杂度。
• 字符串匹配和编辑距离：在涉及字符串操作的应用中，例如查找两个字符串之间的编辑距离或搜索子字符串，记忆化可以通过存储先前计算的结果来帮助避免重新计算相同的子问题。
• 优化问题：许多优化问题涉及为最佳解决方案探索庞大的搜索空间。记忆化可用于存储评估不同解决方案的结果，从而在搜索过程中避免了重新评估相同的解决方案。
• 递归树遍历：在递归遍历树（例如，在二叉树中）时，可以使用记忆化来存储遍历子树的结果，确保同一子树不会被多次遍历。
• 数值计算：记忆化对于涉及昂贵数值计算的函数很有用。通过缓存特定输入值的ョ结果，函数可以避免在后续调用中重新计算这些值。
• 博弈论和人工智能：在游戏和人工智能算法中，记忆化可以帮助存储状态及其对应的值，以避免在决策过程中进行重复评估，从而提高效率。

总之，记忆化是一种通过结果缓存来避免重复计算以优化计算效率的技术。它对于递归算法特别有效，可以将耗时的过程转变为更易于管理和更快的ョ操作。通过智能地存储和重用函数结果，程序员可以创建更高效、响应更快的应用程序。

C++ 中斐波那契数列的记忆化版本程序

输出

Fibonacci number is 102334155
.............................
Process executed in 0.11 seconds
Press any key to continue

说明

1. 该代码使用记忆化方法计算第 n 个斐波那契数。
2. 它包括 C++ 标准库所需的头文件（#include <bits/stdc++.h>）。
3. 定义了两个符号常量：NIL 设置为 -1，MAX 设置为 100。
4. 声明了一个大小为 MAX 的整型数组 lookup，用于存储记忆化的斐波那契值。
5. _initialize() 函数使用 NIL 值初始化 lookup 数组。
6. fib(int n) 函数计算第 n 个斐波那契数
   • 它检查 lookup[n] 的值是否为 NIL。如果是，则计算斐波那契数。
   • 如果 n 为 0 或 1，则将 lookup[n] 赋值为 n。
   • 否则，递归计算 fib(n - 1) + fib(n - 2) 并将结果存储在 lookup[n] 中。
   • 函数返回存储在 lookup[n] 中的值。

C 语言中斐波那契数列的记忆化版本程序

输出

Fibonacci number is 102334155
.............................
Process executed in 0.11 seconds
Press any key to continue

说明

1. 包含用于 printf 等函数的标准输入/输出库。
2. 使用预处理器指令将 NIL 定义为 -1，将 MAX 定义为 100。
3. 声明一个大小为 MAX 的整型数组 lookup，用于存储记忆化的斐波那契值。
4. 定义 _initialize() 函数
   • 初始化一个变量 i。
   • 循环遍历索引 0 到 MAX - 1。
   • 将 lookup 数组中的每个元素设置为 NIL。
5. 定义 fib(int n) 函数来计算第 n 个斐波那契数
   • 检查 lookup[n] 的值是否为 NIL。
   • 如果未初始化
   • 如果 n 为 0 或 1，则将 lookup[n] 设置为 n（基本情况）。
   • 否则，递归计算 fib(n - 1) + fib(n - 2) 并将结果存储在 lookup[n] 中。
6. 定义 main() 函数
   • 声明一个整型变量 n 并将其设置为 40。
   • 调用 _initialize() 来初始化 lookup 数组。
   • 使用 printf 计算并打印第 n 个斐波那契数。
7. 从 main() 函数返回 0，表示程序成功执行。
8. 程序结束。

此 C 代码使用记忆化来高效地计算和打印第 40 个斐波那契数。

时间和空间复杂度分析

时间复杂度

• 影响时间复杂度这里的关键因素是我们需要的唯一子问题的数量。
• 在 fib 函数中，每个斐波那契数只计算一次并存储在 lookup 数组中。后续对同一值的计算直接从 lookup 数组中检索。
• 由于每个斐波那契数只计算一次，因此使用记忆化计算第 n 个斐波那契数的时间复杂度是线性的，可以近似为 O(n)。
• fib 函数中的递归调用通过依赖 lookup 数组中存储的值来避免重复计算。

空间复杂度

• 该代码中空间复杂度的主要贡献者是 lookup 数组中记忆化值的存储。
• lookup 数组存储了 MAX（在本例中为 100）以下的斐波那契数的计算值。
• 因此，代码的空间复杂度为 O(MAX)，其中 MAX 是一个常数值。

总结

制表法

动态规划是一种强大的技术，用于通过将问题分解为更小的子问题并重用这些子问题的解决方案来高效地解决问题。制表是动态规划中一种基本的方法，它涉及使用自底向上的方法迭代地解决问题。在这种方法中，首先计算较小子问题的解决方案，然后使用这些解决方案来构建较大问题的解决方案。这种方法特别适用于优化问题，与朴素的递归方法相比，可以显著提高时间复杂度。

理解制表法

制表法涉及创建一个表（通常是数组或矩阵）来系统地存储子问题的解决方案。表中的每个条目对应于特定子问题的解决方案。表是迭代填充的，从基本情况开始，然后逐渐构建更复杂子问题的解决方案，直到获得原始问题的最终解决方案。

制表法的关键步骤

• 识别子问题：将原始问题分解为更小的、重叠的子问题。每个子问题都应该可以独立求解，并且其解决方案应有助于解决更大的问题。
• 定义基本情况：识别最简单的子问题，可以直接解决而无需进一步分解。这些通常是表格的初始值。
• 初始化表格：创建一个表（通常是数组或矩阵）来存储子问题的解决方案。使用基本情况值初始化表格。
• 迭代计算：以一致的顺序（通常是从左到右，从上到下）开始迭代表格。使用先前已解决子问题的解决方案来计算每个子问题的解决方案。这涉及到应用一个递归关系，该关系定义了子问题解决方案之间的关系。
• 更新表格：在迭代过程中填写表格，逐渐解决越来越大的子问题，直到达到原始问题的最终解决方案。
• 最终解决方案：原始问题的解决方案通常可以在表格的最后一个条目中找到，或者在一个代表所需解决方案的特定条目中找到。

制表法的优点

• 最优子结构：制表法固有地利用了最优子结构属性，其中一个更大问题的解决方案可以通过较小子问题的解决方案来构建。
• 避免重新计算：与朴素的递归方法不同，制表法通过将子问题的解决方案存储在表中来避免重复计算。这可以为具有重叠子问题的ョ问题节省大量时间。
• 改进的时间复杂度：与朴素的递归方法相比，制表法通常具有更低的时间复杂度，这使得它在解决复杂问题方面更有效。
• 内存效率：由于表只存储必需的子问题解决方案，因此它通常比存储所有子问题解决方案的记忆化（另一种动态规划技术）需要更少的内存。

动态规划中的制表法是一种系统而高效的方法，通过将复杂问题分解为更小、易于管理的子问题来解决它们。通过使用解决方案迭代地填充表，该方法可以最优地构建原始问题的解决方案。这项技术被广泛应用于计算机科学、数学、优化和算法设计等各个领域，以高效地解决问题并避免重复计算。理解制表的原理能够使程序员能够应对挑战性问题并开发出高效的算法。

以下是制表法的程序

输出

Fibonacci number is 34
………………………………..
Process executed in 0.05 seconds
Press any key to continue.

说明

• 这包括输入和输出操作所需的头文件（iostream），并且还使用了 std 命名空间，这允许您使用标准的 C++ 库函数而无需每次都指定命名空间。
• 这定义了一个 int fib(int n) 函数，该函数使用制表方法（自底向上动态规划）计算第 n 个斐波那契数。
• 它以一个整数 n 作为参数，该参数指定要计算的斐波那契数的索引。
• 在函数内部
• 声明了一个大小为 n + 1 的整型数组 f，用于存储斐波那契数。
• 前两个斐波那契数 f[0] 和 f[1] 被显式设置为 0 和 1。
• 一个循环从索引 2 到 n 进行迭代，在每次迭代中，通过将前两个斐波那契数 f[i - 1] 和 f[i - 2] 相加来计算 f[i] 的值。
• 这是 main 函数，程序执行从这里开始。
• 在 main 函数内部
• 整数 n 被赋值为 9，表示要计算第 9 个斐波那契数。
• printf 函数用于打印 fib(n) 函数的结果，该函数计算第 9 个斐波那契数。
• return 0; 语句表示程序成功执行。
• 总而言之，该代码使用制表法计算并打印第 9 个斐波那契数，对于较大的斐波那契数，这比朴素的递归方法更有效。制表法通过存储先前计算的斐波那契数来避免重复计算。

时间和空间复杂度分析

让我们分析一下该程序的时间和空间复杂度。

时间复杂度分析

该程序的时间复杂度主要由从 2 到 n 的循环决定。在循环内部，每个斐波那契数的计算需要恒定的时间（将最后两个已计算的斐波那契数相加）。因此，时间复杂度可以近似为 O(n)，其中 n 是表示所需斐波那契数索引的输入值。

空间复杂度分析

程序的空间复杂度由用于制表的数组 f[] 决定。该数组存储从 0 到 n 的计算斐波那契数。由于数组大小与输入值“n”成正比，因此空间复杂度为 O(n)。

总之，给定的程序具有 O(n) 的时间复杂度和 O(n) 的空间复杂度。时间复杂度表示程序的执行时间随输入值“n”线性增长。类似地，空间复杂度意味着由于数组中制表斐波那契数的存储，内存使用量也随输入值线性增加。