动态规划简介

Created: November-22, 2018

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

我们来看一个例子。我们通常称为 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) 没有任何影响，则该问题不具有最佳子结构。简单来说，如果问题的最优解可以从其子问题的最优解中找到，那么我们可以说问题具有最优的子结构性质。