动态规划简介

动态编程通过将解决方案与子问题相结合来解决问题。它可以类似于分而治之的方法,其中问题被划分为不相交的子问题,子问题被递归地求解,然后组合以找到原始问题的解。相反,动态编程在子问题重叠时适用 - 也就是说,当子问题共享子问题时。在这种情况下,分而治之的算法比必要的工作更多,重复解决常见的子问题。动态编程算法只解决每个子子问题一次,然后将其答案保存在表中,从而避免每次解决每个子子问题时重新计算答案的工作。

我们来看一个例子。我们通常称为 Fibonacci 的意大利数学家 Leonardo Pisano Bigollo 通过考虑兔子种群理想化增长发现了一系列。该系列是:

1, 1, 2, 3, 5, 8, 13, 21, ......

我们可以注意到前两个后面的每个数字都是前面两个数字的总和。现在,让我们制定一个函数 F(n) ,它将返回第 n 个 Fibonacci 数,这意味着,

F(n) = nth Fibonacci Number

到目前为止,我们已经知道,

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

我们可以通过以下方式概括:

F(1) = 1
F(2) = 1
F(n) = F(n-1) + F(n-2)

现在,如果我们想将它写为递归函数,我们将 F(1)F(2) 作为基本情况。所以我们的 Fibonacci 函数将是:

Procedure F(n):                //A function to return nth Fibonacci Number
if n is equal to 1
    Return 1
else if n is equal to 2
    Return 1
end if
Return F(n-1) + F(n-2)

现在,如果我们调用 F(6),它将调用 F(5)F(4),这将调用更多。让我们以图形方式表示:

https://i.stack.imgur.com/ngSbS.jpg

从图中可以看出,F(6) 将调用 F(5)F(4)。现在 F(5) 将调用 F(4)F(3)。在计算 F(5) 之后,我们可以肯定地说已经计算了 F(5) 调用的所有函数。这意味着,我们已经计算了 F(4)。但我们再次计算 F(4),因为 F(6) 的右孩子指示。我们真的需要重新计算吗?我们可以做的是,一旦我们计算了 F(4) 的值,我们就将它存储在一个名为 dp 的数组中,并在需要时重用它。我们将使用 -1 (或我们计算中不会出现的任何值) 初始化我们的 dp 数组。然后我们将调用 F(6) ,其中我们修改的 F(n) 将如下所示: **** **** ****

Procedure F(n):
if n is equal to 1
    Return 1
else if n is equal to 2
    Return 1
else if dp[n] is not equal to -1            //That means we have already calculated dp[n]
    Return dp[n]
else
    dp[n] = F(n-1) + F(n-2)
    Return dp[n]
end if

我们完成了与以前相同的任务,但只进行了简单的优化。也就是说,我们使用了 memoization 技术。首先, dp 数组的所有值都是 -1 。当调用 F(4) 时,我们检查它是否为空。如果它存储 -1 ,我们将计算其值并将其存储在 dp [4]中。如果它存储除 -1 以外的任何东西,那意味着我们已经计算了它的值。所以我们只需返回值。

使用 memoization 的这种简单优化称为动态编程

如果动态编程具有某些特征,则可以解决该问题。这些是:

  • 子问题:
    DP 问题可以分为一个或多个子问题。例如:F(4) 可以分为更小的子问题 F(3)F(2)。由于子问题类似于我们的主要问题,这些可以使用相同的技术来解决。
  • 重叠子问题:
    DP 问题必须具有重叠的子问题。这意味着必须有一些共同的部分,不止一次调用相同的函数。例如:F(5)F(6) 共有 F(3)F(4)。这就是我们将值存储在数组中的原因。

https://i.stack.imgur.com/7OVJm.jpg

  • 最佳子结构:
    假设你被要求最小化功能 g(x)。你知道 g(x) 的价值取决于 g(y)g(z)。现在,如果我们可以通过最小化 g(y)g(z) 来最小化 g(x),那么我们就可以说问题具有最优的子结构。如果通过仅最小化 g(y) 来最小化 g(x) 并且如果最小化或最大化 g(z)g(x) 没有任何影响,则该问题不具有最佳子结构。简单来说,如果问题的最优解可以从其子问题的最优解中找到,那么我们可以说问题具有最优的子结构性质。