构建 DP 解决方案

Created: November-22, 2018

无论你使用动态编程（DP）解决了多少问题，它仍然会让你感到惊讶。但作为生活中的其他一切，练习会让你变得更好。记住这些，我们将看看构建 DP 问题解决方案的过程。有关此主题的其他示例将帮助你了解 DP 是什么以及它是如何工作的。在此示例中，我们将尝试了解如何从头开始提供 DP 解决方案。

迭代 VS 递归：
有两种构造 DP 解决方案的技术。他们是：

迭代（使用 for-cycles）
递归（使用递归）

例如，用于计算两个字符串 s1 和 s2 的最长公共子序列的长度的算法如下所示： **** ****

Procedure LCSlength(s1, s2):
Table[0][0] = 0
for i from 1 to s1.length
    Table[0][i] = 0
endfor
for i from 1 to s2.length
    Table[i][0] = 0
endfor
for i from 1 to s2.length
    for j from 1 to s1.length
        if s2[i] equals to s1[j]
            Table[i][j] = Table[i-1][j-1] + 1
        else
            Table[i][j] = max(Table[i-1][j], Table[i][j-1])
        endif
    endfor
endfor
Return Table[s2.length][s1.length]

这是一个迭代的解决方案。以这种方式编码的原因有几个：

迭代比递归更快。
确定时间和空间复杂性更容易。
源代码简短而干净

查看源代码，你可以轻松了解其工作原理和原因，但很难理解如何提出此解决方案。然而，上述两种方法转换为两种不同的伪代码。一个使用迭代（Bottom-Up），另一个使用递归（Top-Down）方法。后者也称为记忆技术。然而，这两种解决方案或多或少是等价的，并且可以很容易地转换成另一种解决方案。在本例中，我们将展示如何为问题提出递归解决方案。

示例问题：
假设你将 N （ 1,2,3，….，N ）葡萄酒放在架子上彼此相邻。我的葡萄酒的价格是 p [i] 。葡萄酒的价格每年都在上涨。假设这是第 1 年，在第 y 年，第 i 个葡萄酒的价格将是：年份*葡萄酒的价格= y * p [i] 。你想要出售你所拥有的葡萄酒，但从今年开始，你每年必须出售一种葡萄酒。同样，每年，你只能出售最左边或最右边的葡萄酒，而不能重新排列葡萄酒，这意味着它们必须保持与开始时相同的顺序。

例如：假设你在货架上有 4 种葡萄酒，价格是（从左到右）：

+---+---+---+---+
| `1` | 4 | 2 | 3 |
+---+---+---+---+

最佳解决方案是以 1 - > 4 - > 3 - > 2 的顺序出售葡萄酒，这将为我们带来以下总利润： StackOverflow 文档

贪婪的方法：
经过一段时间的头脑风暴，你可能会想出尽可能晚地出售昂贵的葡萄酒的解决方案。所以你的贪婪策略将是：

Every year, sell the cheaper of the two (leftmost and rightmost) available wines.

尽管该策略没有提及当两种葡萄酒的成本相同时该怎么做，但这种策略有点合适。但不幸的是，事实并非如此。如果葡萄酒的价格是：

+---+---+---+---+---+
| `2` | 3 | 5 | 1 | 4 |
+---+---+---+---+---+

贪婪的策略会以 1 - > 2 - > 5 - > 4 - > 3 的顺序出售它们，总利润为： StackOverflow 文档

但是，如果我们以 1 - > 5 - > 4 - > 2 - > 3 的顺序出售葡萄酒，我们可以做得更好，总利润为： StackOverflow 文档

这个例子应该让你相信这个问题并不像第一眼看上去那么容易。但它可以使用动态编程来解决。

回溯：
为找到回溯解决方案的问题提出 memoization 解决方案非常方便。Backtrack 解决方案评估问题的所有有效答案并选择最佳答案。对于大多数问题，更容易提出这样的解决方案。在处理回溯解决方案时可以遵循三种策略：

它应该是一个使用递归计算答案的函数。
它应该返回带有 return 语句的答案。
所有非局部变量都应该用作只读，即函数只能修改局部变量及其参数。

对于我们的示例问题，我们将尝试出售最左边或最右边的葡萄酒并递归计算答案并返回更好的答案。回溯解决方案看起来像：

// year represents the current year
// [begin, end] represents the interval of the unsold wines on the shelf
Procedure profitDetermination(year, begin, end):
if begin > end                  //there are no more wines left on the shelf
    Return 0
Return max(profitDetermination(year+1, begin+1, end) + year * p[begin], //selling the leftmost item
           profitDetermination(year+1, begin, end+1) + year * p[end])   //selling the rightmost item

如果我们使用 profitDetermination(1, 0, n-1) 调用该程序，其中 n 是葡萄酒的总数，它将返回答案。

这个解决方案只是尝试销售葡萄酒的所有可能的有效组合。如果一开始就有 n 种葡萄酒，它将检查 StackOverflow 文档可能性。即使我们现在得到正确答案，算法的时间复杂度也呈指数级增长。

正确编写的回溯函数应始终代表一个明确问题的答案。在我们的例子中，程序 profitDetermination 代表了一个问题的答案： *当今年是年份并且未售出的葡萄酒的间隔跨越[开始]时，我们可以通过销售存储在数组 p 中的价格获得的最佳利润是多少？，结束]，包容性？*你应该总是尝试为你的回溯函数创建一个这样的问题，看看你是否正确，并确切了解它的作用。

确定状态：
状态是 DP 解决方案中使用的参数数量。在这一步中，我们需要考虑传递给函数的哪些参数是多余的，即我们可以从其他参数构造它们，或者根本不需要它们。如果有任何这样的参数，我们不需要将它们传递给函数，我们将在函数内部计算它们。

在上面显示的示例函数 profitDetermination 中，参数 year 是冗余的。它相当于我们已售出的葡萄酒数量加一。可以使用从开始的葡萄酒总数减去我们未售出的葡萄酒数量加上一个来确定。如果我们将葡萄酒总数 n 存储为全局变量，我们可以将函数重写为：

Procedure profitDetermination(begin, end):
if begin > end
    Return 0
year := n - (end-begin+1) + 1        //as described above
Return max(profitDetermination(begin+1, end) + year * p[begin],
           profitDetermination(begin, end+1) + year * p[end])

我们还需要考虑可以从有效输入获得的参数的可能值范围。在我们的示例中，begin 和 end 中的每个参数都可以包含从 0 到 n-1 的值。在有效的输入中，我们也期望 begin <= end + 1。可以使用 O(n²) 不同的参数调用我们的函数。

记忆：
我们现在差不多完成了。为了将具有时间复杂度的回溯解决方案转换为具有时间复杂度的 StackOverflow 文档 memoization 解决方案，我们将使用一个不需要太多努力的小技巧。

如上所述，只有 StackOverflow 文档不同的参数可以调用我们的函数。换句话说，我们实际上只能计算不同的东西。那么时间复杂性来自何处以及它的计算内容！

答案是：指数时间复杂度来自重复递归，因此，它一次又一次地计算相同的值。如果你为 n = 20 个葡萄酒的任意数组运行上面提到的代码，并计算为参数 begin = 10 和 end = 10 调用函数的次数，你将得到一个数字 92378 。多次计算相同的答案是浪费大量时间。我们可以做些什么来改进它，一旦我们计算了它们就存储了值，每次函数请求已经计算的值时，我们不需要再次运行整个递归。我们将有一个数组 dp [N] [N] ，用 -1 （或我们的计算中不会出现的任何值）初始化它，其中 -1 表示尚未计算的值。数组的大小由 begin 和 end 的最大可能值决定，因为我们将在数组中存储某些 begin 和 end 值的相应值。我们的程序如下：

Procedure profitDetermination(begin, end):
if begin > end
    Return 0
if dp[begin][end] is not equal to -1                //Already calculated
    Return dp[begin][end]
year := n - (end-begin+1) + 1
dp[begin][end] := max(profitDetermination(year+1, begin+1, end) + year * p[begin],
           profitDetermination(year+1, begin, end+1) + year * p[end])
Return dp[begin][end]

这是我们所需的 DP 解决方案。使用我们非常简单的技巧，解决方案运行 StackOverflow 文档时间，因为有不同的参数可以调用我们的函数，对于每个参数，函数只运行一次复杂。

总结：
如果你可以确定可以使用 DP 解决的问题，请使用以下步骤构建 DP 解决方案：

创建回溯功能以提供正确答案。
删除多余的参数。
估计并最小化函数参数的可能值的最大范围。
尝试优化一个函数调用的时间复杂度。
存储值，以便你不必计算两次。

在一个 DP 溶液的复杂性是： 可能值的范围中的功能可与被称为 * 时间每次调用的复杂性。