动态规划
动态规划
动态规划是一种设计算法的方法。
使用动态规划设计的算法将问题分解成子问题,找到子问题的解,并将它们组合在一起,形成我们要解决的问题的完整解决方案。
要使用动态规划为问题设计算法,我们要解决的问题必须具有以下两个属性
- 重叠子问题:表示问题可以分解成更小的子问题,其中子问题的解是重叠的。 具有重叠子问题意味着一个子问题的解是另一个子问题的解的一部分。
- 最优子结构:表示问题的完整解可以从其较小子问题的解构建而成。 所以问题不仅必须具有重叠子问题,子结构也必须是最优的,这样才能将子问题的解组合在一起形成完整解。
在本教程中,我们已经在 记忆化 和 表格化 技术中看到了动态规划,以及用于解决诸如 0/1 背包问题 或找到 最短路径 的问题 Bellman-Ford 算法。
注意:设计算法的另一种方法是使用 贪心 方法。
使用动态规划找到第 \(n\) 个斐波那契数
假设我们想要一个找到第 \(n\) 个斐波那契数的算法。 我们还不知道如何找到第 \(n\) 个斐波那契数,只是我们想使用动态规划来设计算法。
斐波那契数 是一个从 \(0\) 和 \(1\) 开始的数字序列,后续的数字由前两个数字相加得到。
前 8 个斐波那契数是:\(0,\; 1,\; 1,\; 2,\; 3,\; 5,\; 8,\; 13\)。
从 0 开始计数,第 \(4\) 个斐波那契数 \(F(4)\) 是 \(3\)。
一般来说,这是根据前两个数字创建斐波那契数的方式
\[ F(n)=F(n-1)+F(n-2) \]
那么我们如何使用动态规划来设计一个找到第 \(n\) 个斐波那契数的算法呢?
对于如何使用动态规划设计算法没有确切的规则,但以下建议在大多数情况下应该有效
- 检查问题是否具有“重叠子问题”和“最优子结构”。
- 解决最基本的子问题。
- 找到一种方法将子问题解组合在一起,形成新子问题的解。
- 编写算法(分步程序)。
- 实现算法(测试是否有效)。
让我们来做吧。
步骤 1:检查问题是否具有“重叠子问题”和“最优子结构”。
在尝试使用动态规划找到算法之前,我们必须首先检查问题是否具有“重叠子问题”和“最优子结构”这两个属性。
重叠子问题?
是的。 第 \(6\) 个斐波那契数是第 \(5\) 个和第 \(4\) 个斐波那契数的组合:\(8=5+3\)。 并且此规则适用于所有其他斐波那契数。 这表明找到第 \(n\) 个斐波那契数的问题可以分解成子问题。
此外,子问题是重叠的,因为 \(F(5)\) 基于 \(F(4)\) 和 \(F(3)\),而 \(F(6)\) 基于 \(F(5)\) 和 \(F(4)\)。
\[ \begin{equation} \begin{aligned} F(5) {} & =\underline{F(4)}+F(3) \\ 5 & =\underline{3}+2 \\\\ & and \\\\ F(6) & =F(5)+\underline{F(4)} \\ 8 & =5+\underline{3} \end{aligned} \end{equation} \]
看到了吗? \(F(5)\) 和 \(F(6)\) 的两个子问题解都是使用 \(F(4)\) 的解创建的,并且有许多这样的情况,因此子问题也是重叠的。
最优子结构?
是的,斐波那契数列具有非常清晰的结构,因为前两个数字相加得到下一个斐波那契数,并且这适用于除前两个之外的所有斐波那契数。 这意味着我们知道如何通过组合子问题的解来构建一个解。
我们可以得出结论,找到第 \(n\) 个斐波那契数的问题满足这两个要求,这意味着我们可以使用动态规划来找到一个解决该问题的算法。
步骤 2:解决最基本的子问题。
我们现在可以开始尝试使用动态规划来找到算法。
首先解决最基本的子问题是一个很好的起点,可以了解算法应该如何运行。
在我们找到第 \(n\) 个斐波那契数的问题中,找到最基本的子问题并不难,因为我们已经知道
\[ F(0)=0 \\ F(1)=1 \\ F(2)=1 \\ F(3)=2 \\ F(4)=3 \\ F(5)=5 \\ F(6)=8 \\ ... \]
步骤 3:找到一种方法将子问题解组合在一起,形成新子问题的解。
在这一步中,对于我们的问题,子问题的组合方式非常简单,我们只需要将前两个斐波那契数相加就可以找到下一个斐波那契数。
例如,第 \(2\) 个斐波那契数是通过将前两个数字 \(F(2)=F(1)+F(0)\) 相加得到的,这也是通用的规则,如前所述:\(F(n)=F(n-1)+F(n-2)\)。
注意:在其他问题中,将子问题的解组合在一起形成新解通常涉及做出决策,例如“我们应该选择这条路还是那条路?”,或者“我们应该包含这个项目还是不包含这个项目?”。
步骤 4:编写算法(分步程序)。
与其直接编写算法的文本,不如先尝试编写一个解决特定问题的过程,例如找到第 \(6\) 个斐波那契数。
作为参考,前 8 个斐波那契数是:\(0,\; 1,\; 1,\; 2,\; 3,\; 5,\; \underline{8},\; 13\)。
要找到第 \(6\) 个斐波那契数,我们可以从序列中位置 0 和 1 的两个第一个数字 \(0\) 和 \(1\) 开始,并将它们放入数组中,分别在索引 0 和 1。 然后,我们可以将数组中的前两个数字相加,生成下一个数字,并将该新数字作为新元素推入数组。 如果我们像这样继续,直到数组长度为 7,我们就停止并返回 F[6]
。 那会起作用,对吧?
在解决上述特定问题后,现在更容易编写实际的算法。
使用动态规划作为设计方法,找到第 \(n\) 个斐波那契数的算法可以描述如下
工作原理
- 创建一个具有 \(n+1\) 个元素的数组
F
。 - 存储前两个斐波那契数
F[0]=0
和F[1]=1
。 - 存储下一个元素
F[2]=F[1]+F[0]
,并继续像这样创建新的斐波那契数,直到创建F[n]
中的值。 - 返回
F[n]
。
步骤 5:实现算法(测试是否有效)。
为了实现上述算法,我们假设函数的参数n
是一个正数(第 \(n\) 个斐波那契数),我们使用一个 for
循环来创建新的斐波那契数,如果函数被调用时参数为 0
或 1
,我们直接返回基本情况 F[0]
和 F[1]
。
实现算法也意味着我们可以检查它是否有效。
示例
使用我们新的算法找到第 6 个斐波那契数
def nth_fibo(n):
if n==0: return 0
if n==1: return 1
F = [None] * (n + 1)
F[0] = 0
F[1] = 1
for i in range(2, n + 1):
F[i] = F[i - 1] + F[i - 2]
return F[n]
n = 6
result = nth_fibo(n)
print(f"The {n}th Fibonacci number is {result}")
运行示例 »
找到了!
我们已经使用动态规划作为设计方法来创建一种算法,用于查找第 \(n\) 个斐波那契数。
我们还实现了该算法来证明它有效,在此过程中,我们无意中使用了一种在动态规划中被称为 表格法 的成熟技术,其中解决方案是通过自下而上地解决子问题,并使用某种表格来找到的。
此外,我们避免了多次计算相同的重叠子问题,例如 F[3]
,否则,我们可能会使用 蛮力递归方法 来解决。
动态规划中使用的另一种技术称为 记忆化。在这种情况下,使用记忆化实质上是使用蛮力递归地解决了问题,但在算法运行时存储子问题解决方案,以避免多次进行相同的计算。
动态规划中使用的技术
使用动态规划设计算法可能很困难,但动态规划的概念实际上并不难:解决问题,但由于子问题是重叠的,所以要以一种聪明的方式来做,这样特定子问题只需要解决一次。
为了能够在动态规划中使用对先前解决的子问题的解决方案,必须以某种方式存储先前找到的解决方案,这可以通过使用 记忆化 或 表格法 来实现。
记忆化是动态规划中使用的一种技术,其中解决方案是通过递归找到的。当算法运行时,子问题的解决方案被存储,并且在尝试计算子问题的解决方案之前,它首先检查该解决方案是否已经计算出来,以避免多次进行相同的计算。
记忆化技术被称为“自顶向下”,因为初始函数调用用于主要问题,并且它会导致新的函数调用来解决越来越小的子问题。
表格法是动态规划中使用的一种技术,其中对重叠子问题的解决方案存储在一个表(数组)中,从最基本的子问题开始。
表格法不是递归的,它被称为“自底向上”,因为最终解决方案的构建方式是首先解决最基本的子问题。由于最基本的子问题的解决方案首先存储在表中,因此在以后解决依赖于先前子问题的子问题时,算法可以直接从表中获取这些解决方案,无需再次计算它们。
为了更好地了解记忆化是如何工作的,它被认为是“自顶向下”的,以及表格法是如何工作的,它是“自底向上”的,请查看下面的两张图片。
如您在上面的图片中看到的,表格法从底部开始,首先解决 F(0),而记忆化方法从顶部开始,使用 F(10) 并从那里将其分解成越来越小的子问题。