dynamic-programming动态编程入门


备注

本节概述了动态编程是什么,以及开发人员可能想要使用它的原因。

它还应该提到动态编程中的任何大型主题,并链接到相关主题。由于动态编程的文档是新的,您可能需要创建这些相关主题的初始版本。

动态规划简介

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

我们来看一个例子。我们通常称为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) ,这将调用更多。让我们以图形方式表示:

F的递归树(6)

从图中可以看出, 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) 的共同点。这就是我们将值存储在数组中的原因。

重叠子问题图

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

构建DP解决方案

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

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

  • 迭代(使用for-cycles)
  • 递归(使用递归)

例如,用于计算两个字符串s1s2最长公共子序列的长度的算法如下所示:

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)方法。后者也称为记忆技术。然而,这两种解决方案或多或少是等价的,并且可以很容易地转换成另一种解决方案。在本例中,我们将展示如何为问题提出递归解决方案。

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

例如:假设您在货架上有4种葡萄酒,价格是(从左到右):

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

最佳解决方案是以1 - > 4 - > 3 - > 2的顺序出售葡萄酒,这将为我们带来以下总利润: 11 + 32 + 23 + 44 = 29

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

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

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

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

贪婪的策略会以1 - > 2 - > 5 - > 4 - > 3的顺序出售它们,总利润为: 21 + 32 + 43 + 14 + 5 * 5 = 49

但是,如果我们以1 - > 5 - > 4 - > 2 - > 3的顺序出售葡萄酒,我们可以做得更好,总利润为: 21 + 42 + 13 + 34 + 5 * 5 = 50

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

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

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

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

// 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种葡萄酒,它会检查2 ^ N可能性。即使我们现在得到正确答案,算法的时间复杂度也呈指数级增长。

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

确定国家:
State是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])
 

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

记忆化:
我们现在差不多完成了。以时间复杂度转换回溯解决方案O(2 ^ n)的到具有时间复杂性的memoization解决方案为O(n ^ 2) ,我们将使用一个不需要太多努力的小技巧。

如上所述,只有为O(n ^ 2)不同的参数可以调用我们的函数。换句话说,只有为O(n ^ 2)我们实际可以计算出不同的东西那么哪里呢O(2 ^ n)的时间复杂性来自于它的计算!

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

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解决方案。通过我们非常简单的技巧,解决方案运行为O(n ^ 2)时间,因为有为O(n ^ 2)不同的参数我们的函数可以调用,对于每个函数,函数只运行一次O(1)复杂。

综述:
如果您可以确定可以使用DP解决的问题,请使用以下步骤构建DP解决方案:

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

DP解决方案的复杂性是: 可以通过 每次调用的时间复杂度 来调用函数的可能值的范围

理解动态规划中的状态

我们来举个例子来讨论一下。从n个项目中,你可以有多少种选择[R色的物品?你知道它表示nCr的 。现在想想一个单项。

  • 如果您没有选择该项目,那么您必须从剩余的n-1项目中获取r项目,该项目由第(n-1)的Cr
  • 如果您选择该项目,则必须从剩余的n-1项目中获取r -1项目,该项目由第(n-1)C(R-1)

这两者的总和给出了我们总的方式。那是:
nCr =(n-1)Cr +(n-1)C(r-1)

如果我们认为nCr(n,r) 是一个以nr 为参数并确定的函数nCr的 ,我们可以把上面提到的关系写成:

nCr(n,r) = nCr(n-1,r) + nCr(n-1,r-1)
 

这是一种递归关系。要终止它,我们需要确定基本情况。我们知道, nC1 = nnCn = 1 。使用这两个作为基本情况,我们的算法来确定nCr的将会:

Procedure nCr(n, r):
if r is equal to 1
    Return n
else if n is equal to r
    Return 1
end if
Return nCr(n-1,r) + nCr(n-1,r-1)
 

如果我们以图形方式查看过程,我们可以看到一些递归被多次调用。例如:如果我们取n = 8r = 5 ,我们得到:

显示重叠子问题的递归树

我们可以通过使用数组dp来避免这种重复调用。由于有2个参数,我们需要一个2D数组。我们将使用-1初始化dp数组,其中-1表示尚未计算的值。我们的程序将是:

Procedure nCr(n,r):
if r is equal to 1
    Return n
else if n is equal to r
    Return 1
else if dp[n][r] is not equal to -1        //The value has been calculated
    Return dp[n][r]
end if
dp[n][r] := nCr(n-1,r) + nCr(n-1,r-1)
Return dp[n][r]
 

确定nCr的 ,我们需要两个参数nr 。这些参数称为状态 。我们可以简单地推断出状态的数量决定了dp数组的维数。阵列的大小将根据我们的需要而改变。我们的动态编程算法将保持以下一般模式:

Procedure DP-Function(state_1, state_2, ...., state_n)
Return if reached any base case
Check array and Return if the value is already calculated.
Calculate the value recursively for this state
Save the value in the table and Return
 

确定状态是动态规划中最重要的部分之一。它由定义我们问题的参数数量和优化计算组成,我们可以优化整个问题。