制表 vs 备忘录

实现动态规划有两种方法，或者说，有两种存储子问题解的方法，以便可以重用它们。

• 制表
• 记忆化

让我们一一简要理解每种方法。

什么是制表法？

制表法是一种用于实现 DP 算法的技术。它也被称为自底向上方法。它从解决最低级别的子问题开始。最低级别子问题的解决方案将有助于解决下一个级别的子问题，依此类推。我们通过迭代来解决所有子问题，直到解决完所有子问题。当一个子问题需要解决之前已解决的子问题的解决方案时，此方法可以节省时间。

让我们通过一个例子来理解制表法。

考虑斐波那契数列的一个例子。

假设我们需要计算 F(5) 项。

为了计算 F(5) 项，会出现一些子问题不止一次。例如，F(3) 子问题出现两次，F(4) 子问题出现四次。

尽管反复计算相同的子问题，我们也可以存储一个子问题的结果一次，并在需要时使用该结果。

让我们看看不存储结果的代码。

在上面的代码中，我们只是在不存储结果的情况下计算斐波那契数列。F(0) 和 F(1) 的值分别为 0 和 1。第 n 项的值使用 Fibonacci(n-1)+Fibonacci(n-2) 计算。

上面的代码通过存储所有子问题的结果来计算斐波那契数列。我们使用 F[n] == null 条件来确定结果是否存在于数组中。

什么是记忆化搜索？

记忆化搜索是一种用于实现 DP 算法的技术。记忆化搜索也被称为自顶向下方法。它从解决最高级别的子问题开始。最初，它解决最高级别的子问题，然后递归地解决下一个子问题。假设有两个子问题，即子问题 A 和子问题 B。当递归调用子问题 B 时，它可以利用子问题 A 的已用过的解决方案。由于 A 和所有子问题都被记忆化了，因此它避免了解决 B 产生的整个递归树，并节省了计算时间。

让我们通过斐波那契数列的例子来理解记忆化搜索。

数列中的数字是前两个数字的总和。斐波那契数列是 0, 1, 1, 2, 3, 5, 8, 13 等。

计算斐波那契数列的条件如下

F(n) = 0 if n = 0

1 if n = 1

F(n-1) + f(n-2) if n>1

递归解决方案程序

查找递归解决方案的时间复杂度为 O(2ⁿ)。

记忆化搜索程序

上面的代码用于记忆化搜索。记忆化搜索是一种用于存储所有已解决的子问题，以便我们不必重新计算已解决子问题的解决方案，它还降低了时间复杂度。

让我们理解制表法和记忆化搜索之间的区别。

1. 制表法：制表法是一种用于递归解决子问题的技术。下面的代码显示了制表法的运行情况

假设我们要计算 f(5) 的斐波那契数列。f(5) 的斐波那契数列是 0, 1, 1, 2, 3, 5。计算 f(15) 总共需要 15 次调用。

记忆化搜索：记忆化搜索是一种用于非递归解决子问题的技术。

上面的代码的时间复杂度为 O(2ⁿ)。这个时间复杂度是非线性的。为了降低这个时间复杂度，我们可以使用记忆化搜索技术。这项技术减少了调用次数，并降低了时间复杂度。

2. 状态转移

制表法也称为自底向上方法。它从基本状态 0 开始。一旦解决了基本状态 0，就移动到状态 1。状态 1 需要基本状态 0 的解决方案。一旦解决了状态 1，我们就移动到状态 2。状态 2 需要状态 1 的解决方案。此过程将持续到达到 n 状态。 'n' 状态是目标状态，也被称为向上状态。这就是所谓的状态转移关系。

记忆化搜索也称为自顶向下方法。它从最高状态 n 开始。'n' 状态需要 'n-1' 状态的解决方案，但 'n-1' 状态尚未解决。为了解决其状态，'n-1' 状态需要 'n-2' 状态的解决方案，但 'n-2' 状态尚未解决。它将进一步递归调用，直到达到基本状态。它将进行递归调用，如 f(n), f(n-1), f(n-2), ..., 0, 1。因此，我们在这里从最高状态开始，然后通过递归达到基本状态。

让我们通过一个例子来理解这个概念。

在上图中，'0' 是源顶点，5 是目标顶点。要到达顶点 5，我们可以从 2 或 3 到达。决策将基于顶点之间的距离。假设顶点 (0,2) 之间的距离是 1，(0,3) 之间的距离是 2。如果我们考虑顶点 2，那么从顶点 0 到 5 的距离是 (1+1) = 2。如果我们考虑顶点 3，那么从顶点 0 到 5 的距离是 (2+1) = 3。最小距离是 2，所以我们将考虑顶点 2 来到达顶点 5。

制表法和记忆化搜索之间的区别

以下是制表法和记忆化搜索之间的区别列表