关于贪婪算法、分治法和动态规划的免费电子书

算法书

如何将您的名字添加到贡献者名单中

贪婪算法

使用贪婪算法计算找零

Dijkstra算法

分而治之

动态规划

背包问题

这是我写的一本关于算法设计范式（贪婪算法、分治法和动态规划）的书。免费赠送给你✨

想要格式良好、排版清晰的 PDF 吗？

附赠额外示例、精美图表等。全部免费？

注册下面的我的电子邮件列表，我会把它送给你😁

👆 只需点击上方图片

我的书也在 GitHub 上（只有 LaTeX 代码）。点个 Star！😁

注意：这本书比这篇文章内容更丰富，更新也更及时。快去看看吧！😁

贪婪算法

贪婪算法旨在在特定时刻做出最优选择。它每一步都选择最优方案，而无需预知未来。它试图用这种方法找到解决整个问题的全局最优方案。

贪婪算法为什么叫贪婪？

当算法利用贪婪属性时，它被称为贪婪算法。贪婪属性包括：

在那个确切的时刻，最佳的选择是什么？

贪婪算法是贪婪的。它们不会展望未来来确定全局最优解。它们只关注局部的最优解。这意味着整体最优解可能与算法选择的解不同。

他们从不回顾自己做过的事情，看看自己能否实现全局优化。这就是贪婪算法和动态规划的主要区别。

贪婪算法有什么用处？

贪婪算法非常快，比其他两种算法（分治法和动态规划）快得多。人们之所以使用贪婪算法，就是因为它们速度快。

大多数使用贪婪算法的流行算法都表明，贪婪算法每次都能给出全局最优解。其中包括：

• Dijkstra算法
• Kruskal算法
• Prim算法
• 哈夫曼树

我们将用一个著名的例子——数找零——来探索贪婪算法。这个范式其实没什么特别的。

如何创建贪婪算法？

你的算法需要遵循这个属性：

在那个确切的时刻，最佳的选择是什么？

就是这样。没什么特别的。贪婪算法通常比分治法或动态规划更容易编写。

使用贪婪算法计算找零

想象一下你是一台自动售货机。有人给你1英镑，然后你花0.70英镑买了一杯饮料。英镑里没有30便士的硬币，你怎么计算找零呢？

作为参考，这是英国每种硬币的面值：

1p, 2p, 5p, 10p, 20p, 50p, £1

贪婪算法从最高面额开始，然后反向计算。我们的算法从 1 英镑开始。1 英镑大于 30 便士，所以它不能使用它。它对 50 便士也这样做。它达到了 20 便士。20 便士小于 30 便士，所以它取 1 20 便士。

算法需要返回 10p 的找零。它再次尝试 20p，但 20p > 10p。然后它转到 10p。它选择了 1 10p，现在返回的是 0，我们停止算法。

我们返回 1x20p 和 1x10p。

这个算法在实际生活中效果很好。我们再举一个例子，这次我们在机器里硬币的数量旁边加上面额(denomination, how many)。

(1p, 10), (2p, 3), (5p, 1), (10p, 0), (20p, 1p), (50p, 19p), (100p, 16)

算法再次被要求找零 30 便士。100 便士（1 英镑）不行。50 便士也一样。20 便士，我们可以这样做。我们选择 1 x 20 便士。现在我们需要找零 10 便士。20 便士已经用完了，所以我们向下移动 1。

10p 已经用完了，所以我们减少 1。

我们有 5 便士，所以我们选择 1x5 便士。现在我们需要归还 5 便士。5 便士已经用完了，所以我们向下移动一位。

我们选择 1 枚 2 便士硬币。现在我们需要归还 3 便士。我们选择另一枚 2 便士硬币。现在我们需要归还 1 便士。我们向下移动一枚。

我们选择 1x 1p 硬币。

总的来说，我们的算法选择了这些硬币作为找零：

# (value, how many we return as change)
(10, 1)
(5, 1)
(2, 2)
(1, 1)

让我们写点代码吧。首先，我们需要定义问题。我们从面额开始。

denominations = [1, 2, 5, 10, 20, 50, 100]
# 100p is £1

现在进入核心功能。给定面额和找零金额，我们希望返回该硬币被找零的次数列表。

如果我们的denominations清单如上，则[6, 3, 0, 0, 0, 0, 0]代表取 6 个 1p 硬币和 3 个 2p 硬币，但取 0 个其他硬币。

denominations = [1, 2, 5, 10, 20, 50, 100]
# 100p is £1

def returnChange(change, denominations):
    toGiveBack = [0] * len(denominations)
    for pos, coin in reversed(list(enumerate(denominations))):

我们创建一个列表，其面额长度为 0，并用 0 填充。

我们希望反向循环，从最大到最小。Reversed(x)反转 x 并让我们反向循环。枚举的意思是“循环遍历此列表，但将位置保存在另一个变量中”。在我们的例子中，当我们启动循环时。coin = 100和pos = 6。

下一步是反复选择一枚硬币，直到我们能用为止。如果要给出，change = 40我们希望算法选择 20，然后再选择 20，直到不能再使用 20。我们使用 for 循环来实现。

denominations = [1, 2, 5, 10, 20, 50, 100]
# 100p is £1

def returnChange(change, denominations):
    # makes a list size of length denominations filled with 0
    toGiveBack = [0] * len(denominations)

    # goes backwards through denominations list
    # and also keeps track of the counter, pos.
    for pos, coin in enumerate(reversed(denominations)):
        # while we can still use coin, use it until we can't
        while coin <= change:

当硬币仍可放入找零时，将该硬币添加到我们的退回清单中，toGiveBack并将其从找零中移除。

denominations = [1, 2, 5, 10, 20, 50, 100]
# 100p is £1

def returnChange(change, denominations):
    # makes a list size of length denominations filled with 0
    toGiveBack = [0] * len(denominations)

    # goes backwards through denominations list
    # and also keeps track of the counter, pos.
    for pos, coin in enumerate(reversed(denominations)):
        # while we can still use coin, use it until we can't
        while coin <= change:
            change = change - coin
            toGiveBack[pos] += 1
    return(toGiveBack)

print(returnChange(30, denominations))
# returns [0, 0, 0, 1, 1, 0, 0]
# 1x 10p, 1x 20p

该算法的运行时间由2 个循环决定，因此为 O(n^2)。

贪婪算法是最优的吗？贪婪算法总是有效吗？

它在局部是最优的，但有时并非全局最优。在找零算法中，我们可以强制指定一个非全局最优的点。

实现这一目标的算法是：

• 选择 3 种面值的硬币。1p、x 和小于 2x 但大于 x。

我们将选择 1、15、25。

• 要求找零 2 * 第二种面额 (15)

我们要求找零 30。现在，让我们看看贪婪算法的作用是什么。

[5, 0, 1]

它选择了1x 25p和5x 1p。最优解是2x 15p。

我们的贪婪算法失败了，因为它没有考虑 15 便士。它看了看 25 便士，然后想：“是的，合适。我们就拿去吧。”

然后它看了看 15p 并想“这不合适，我们继续吧”。

这是贪婪算法失败的一个例子。

为了解决这个问题，你要么在行不通的地方创造货币，要么暴力破解。或者使用动态规划。

贪婪算法有时是全局最优的。从前面我们看到，这些算法是全局最优的：

• Dijkstra算法
• Kruskal算法
• Prim算法
• 哈夫曼树

还有其他全局最优解决方案，但贪婪比这些解决方案更快且更容易编程。

Dijkstra算法

迪杰斯特拉算法（Dijkstra's algorithm）用于查找图中从一个节点到其他所有节点的最短路径。在我们的示例中，我们将使用加权有向图。每条边都有一个方向，每条边都有一个权重。

Dijkstra 算法用途广泛。在道路网络中，当需要找到到达某个地点的最快路线时，它非常有用。该算法还用于：

• IP路由
• A*算法
• 电话网络

该算法遵循以下规则：

1. 每次我们要访问一个新节点时，我们都会选择已知距离最小的节点。
2. 一旦我们移动到该节点，我们就会检查它的每个相邻节点。我们通过计算通向该新节点的边的成本之和来计算从相邻节点到根节点的距离。
3. 如果到某个节点的距离小于已知距离，我们将更新最短距离。

第一步是选择起始节点。我们选择 A。所有距离都从无穷大开始，因为我们只有在到达一个知道距离的节点时才知道它们的距离。

我们在未访问节点列表中标记 A。A 到 A 的距离为 0。A 到 B 的距离为 4。A 到 C 的距离为 2。我们更新了右侧的距离列表。

然后，我们选择尚未选择顶点的最小边。最小边是 A -> C，而我们尚未选择 C。我们访问 C。

注意，我们选取​​了当前节点到尚未访问的节点之间的最小距离。我们采用了贪婪算法。在这种情况下，贪婪算法就是全局最优解。

我们可以从 C 到达 B。现在我们需要选择一个最小值。min(4, 2 + 1) = 3。

由于 A -> C -> B 小于 A -> B，我们用这个信息更新 B。然后，我们将现在能够到达的其他节点的距离添加到 B 中。

我们尚未访问的下一个最小顶点是 B，其节点为 3。我们访问 B。

我们对 B 执行相同的操作。然后我们选择尚未访问的最小顶点 D。

这次我们不更新任何距离。那么我们的最后一个节点就是 E。

再次没有更新。为了找到从 A 到其他节点的最短路径，我们回顾一下之前的图。

我们首先选择 A，然后选择 C，然后是 B。如果您需要创建从 A 到每个其他节点的最短路径作为图表，则可以使用右侧的表格运行此算法。

使用此表，可以很容易地绘制出从 A 到图中每个其他节点的最短距离：

使用贪婪算法解决分数背包问题

想象一下你是个小偷。你闯进了1951年奥斯卡最佳女主角奖得主朱迪·霍利迪的家。朱迪是个宝石收藏家。朱迪的房子里堆满了宝石。

你带了一个包——或者说背包。这个包的重量是7。你碰巧从保险单上找到了朱迪所有物品的清单。清单如下：

![]( https://skerritt.blog/content/images/2019/06/Screenshot_2019-06-23-Greedy-Algorithms-1-.png

解决分数背包问题的第一步是计算每件物品的价值/重量。

现在我们贪婪地选择最大的那些。为此，我们可以按照价值/权重降序对它们进行排序。幸运的是，它们已经排好序了。最大的是 3.2。

knapsack value = 16
knapsack total weight = 5 (out of 7)

然后我们选择钫（我知道它不是宝石，但朱迪有点奇怪😉）

knapsack value = 19
knapsack weight = 6

现在，我们添加蓝宝石。但是如果我们添加蓝宝石，我们的总权重将达到 8。

在分数背包问题中，我们可以将物品分割成分数。我们袋子里剩余的重量是 1。我们的蓝宝石重量是 2。我们计算以下比例：

背包剩余重量/物品重量

然后将这个比率乘以物品的价值，得到我们可以拿走该物品的价值。

1/2 * 6 = 3

knapsack value = 21
knapsack weight = 7

贪婪算法可以最优地解决分数背包问题，但无法最优地解决 {0, 1} 背包问题。在这个问题中，你不是取走物品的一小部分，而是要么取 {1}，要么不取 {0}。要解决这个问题，你需要使用动态规划。

该算法的运行时间为O(n log n)。计算值/权重的时间为 O(1)。主要步骤是从最大值/权重开始排序，耗时 O(n log n)。

贪婪、分治、动态规划

结论

贪婪算法速度很快，但可能无法提供最优解。与同类算法相比，贪婪算法也更容易编写代码。

分而治之

分治算法在编程教科书中并不常见，但它是每个程序员都应该了解的。分治算法是并发和多线程的支柱。

我经常听到有人说如何优化 for 循环使其更快，或者 switch 语句比 if 语句略快一些。大多数计算机都有多个核心，能够支持多线程。在担心优化 for 循环或 if 语句之前，不妨尝试从不同的角度来解决问题。

分治法是从不同角度解决问题的方法之一。在本文中，我将讨论如何创建分治解决方案以及它的含义。如果您对此主题没有任何经验或知识，也不用担心。本文旨在供编程知识很少的人阅读。

我将用三个例子来解释这一点。第一个例子会是一个简单的解释。第二个例子会是一些代码。最后一个例子会深入探讨分治法的数学核心。（别担心，我也讨厌数学。）

没时间读这篇文章？ 注册我的邮件列表，即可获取 PDF 格式。你还能获得一些本文未收录的额外内容 ✨点击此处注册。

什么是分而治之？🌎

分而治之就是把一个大问题分解成许多更容易解决的小问题。下面这个相对小的例子就说明了这一点。

我们取“3 + 6 + 2 + 4”这个等式，将其分解成尽可能小的方程组，即[3 + 6, 2 + 4]。它也可以是[2 + 3, 4 + 6]。顺序无关紧要，只要将这个长方程分解成许多更小的方程即可。

假设我们有 8 个数字：

我们要把它们全部加在一起。首先，我们把问题分成8个相等的子问题。具体做法是，把加法分解成单个数字。

然后我们开始一次添加 2 个数字。

然后将 4 个数字变成 8 个数字，这就是我们的结果。

为什么我们在第一阶段就把它分解成单个数字？为什么不直接从第二阶段开始呢？因为虽然这个数字列表是偶数，但如果列表是奇数，你就需要把它分解成单个数字才能更好地处理它。

分治算法试图将问题分解成尽可能多的小块，因为用小块更容易解决。它通常使用递归来实现这一点。

正式地讲，该技术正如Cormen、Leiserson、Rivest 和 Stein在著名的《算法导论》中所定义的那样：

1. 划分

如果问题很小，就直接解决。否则，将问题分解成同一个问题的多个子集。

1. 征服

通过递归求解较小的问题。如果子问题足够小，则无需递归，可以直接求解。

递归是指函数调用自身。如果你以前从未听说过递归，那么理解它可能会比较困难。本页面提供了很好的解释。简而言之，递归函数就是这样的：

n = 6

def recur_factorial(n):
   if n == 1:
       return n
   else:
       return n * recur_factorial(n-1)

print(recur_factorial(n))

我马上就会完整解释该代码。

1. 结合

将子问题的解决方案合并为原始问题的解决方案。

对于上面的代码，需要注意一些重要事项。除法部分也是递归部分。我们将问题划分为return n * recur_factorial(n-1)。

具体来说，该recur_factorial(n-1)部分就是我们将问题进行划分的地方。

征服部分也是递归部分，但也是 if 语句。如果问题足够小，我们就直接求解（通过返回 n）。否则，我们执行return n * recur_factorial(n-1)。

合并。我们用乘法符号来做这件事。最终，我们返回该数的阶乘。如果那里没有这个符号，而它有，那么return recur_factorial(n-1)合并就不会进行，也不会输出任何类似于阶乘的东西。（感兴趣的朋友可以看看，它会输出 1）。

我们将探索分治法在一些著名算法、归并排序和汉诺塔解决方案中的工作原理。

合并排序🤖

归并排序是一种排序算法。该算法的工作原理如下：

• 将 n 个数字的序列分成两半
• 递归地对两半进行排序
• 将两个排序好的部分合并成一个排序好的序列

在这张图中，我们将这 8 个数字分解成单独的数字。就像我们之前做的那样。完成之后，我们就可以开始排序了。

它比较 51 和 13。由于 13 较小，所以它放在左侧。对 (10, 64)、(34, 5)、(32, 21) 都执行了同样的操作。

然后它将 (13, 51) 与 (10, 64) 合并。它知道 13 是第一个列表中最小的，而 10 是右边列表中最小的。10 小于 13，因此我们不需要比较 13 和 64。我们正在比较并合并两个已排序的列表。

在递归中，我们使用“基准情况”来指代我们能够处理的绝对最小值。对于归并排序，基准情况是 1。这意味着我们将列表拆分，直到得到长度为 1 的子列表。这也是为什么我们一直向下到 1 而不是 2。如果基准情况是 2，那么我们会在 2 处停止。

如果列表的长度 (n) 大于 1，那么我们将列表和每个子列表除以 2，直到得到大小为 1 的子列表。如果 n = 1，则列表已经排序，因此我们什么也不做。

归并排序是分治算法的一个例子。让我们再看一个算法，以真正理解分治算法的工作原理。

河内塔🗼

汉诺塔是一个数学问题，它由3个桩子（在本例中是3个圆盘）组成。这个问题主要用于教授递归，但在实际生活中也有一些用途。

每个圆盘的大小都不一样。我们要把所有圆盘都移到C柱上，最大的圆盘放在最下面，第二大的圆盘放在最大的圆盘上面，第三大的圆盘（最小的圆盘）放在所有圆盘的上面。这个游戏有一些规则：

1. 我们每次只能移动 1 个圆盘。
2. 圆盘不能放置在比它小的其他圆盘之上。

我们希望使用尽可能少的移动次数。如果我们有1个圆盘，我们只需要移动一次。如果我们有2个圆盘，我们需要移动3次。

移动次数是 2 的幂减 1。如果我们有 4 个圆盘，我们计算出最少移动次数为 2^4 = 16 - 1 = 15。

为了解决上述示例，我们需要将最小的圆盘存储在缓冲桩中（1 步）。下方动图展示了如何用 3 个桩和 3 个圆盘来解决汉诺塔问题。

请注意我们需要一个缓冲区来存储光盘。

我们可以把这个问题概括一下。假设我们有 n 个圆盘：递归地将 n-1 个圆盘从 A 移动到 B，将最大的圆盘从 A 移动到 C，再递归地将 n-1 个圆盘从 B 移动到 C。

如果棋子数量为偶数，则第一步总是移动到棋盘中间。如果棋子数量为奇数，则第一步总是移动到棋盘另一端。

让我们开始用伪代码编写 ToH 算法。

function MoveTower(disk, source, dest, spare):
    if disk == 0, then:
        move disk from source to dest

我们从一个基本情况开始，disk == 0。source是您开始的挂钩。dest是最终目的地挂钩。spare是备用挂钩。

FUNCTION MoveTower(disk, source, dest, spare):
IF disk == 0, THEN:
    move disk from source to dest
ELSE:
    MoveTower(disk - 1, source, spare, dest) // Step 1
    move disk from source to dest // Step 2
    MoveTower(disk - 1, spare, dest, source) // Step 3
END IF

请注意，在步骤 1 中，我们将dest和互换source。在步骤 3 中，我们不执行此操作。

通过递归，我们可以确定两件事：

1. 它总是有一个基本情况（如果没有，算法如何知道结束？）
2. 该函数调用自身。

算法在第 1 步和第 3 步有点令人困惑。它们都调用了同一个函数。这时就需要多线程了。你可以同时在不同的线程上运行第 1 步和第 3 步。

由于 2 大于 1，我们再次将其向下移动一级。到目前为止，你已经了解了分治法是什么。你应该了解它的工作原理以及代码是什么样子的。接下来，让我们学习如何使用分治法正式定义一个问题的算法。我认为这部分是最重要的。一旦你掌握了这一点，创建分治算法就会变得非常容易。

斐波那契数列🐰

斐波那契数列在自然界中随处可见。兔子的繁殖方式与斐波那契数列类似。2只兔子等于3，3只兔子等于5，5只兔子等于9，以此类推。

数字从 1 开始，下一个数字等于当前数字 + 前一个数字。这里是 1 + 0 = 1。然后 1 + 1 = 2。2 + 1 = 3，以此类推。

我们可以用递归来描述这种关系。递归是一个用较小输入定义函数的方程。递归和递归听起来很相似，实际上也类似。

对于斐波那契数列，如果 n = 0 或 1，结果为 1。否则，递归地将 f(n-1) + f(n -2) 相加，直到到达起始条件。让我们先创建一个非递归的斐波那契数列计算器。

我们知道如果 n = 0 或 1，则返回 1。

def f(n):
    if n == 0 or n == 1:
        return 1

斐波那契数列是最后两个数字相加的结果。

def f(n):
    if n == 0 or n == 1:
        return 1
    else:
    fibo = 1
    fibroPrev = 1
    for i in range (2, n):
        temp = fibo
        fibo = fibo + fiboPrev
        fiboPrev = temp
        return fibo

现在我们已经看到了这一点，让我们使用递归将其转换为递归。

创建递归时，我们总是从基本情况开始。这里的基本情况是，如果 n == 0 或 1，则返回 n。

如果我们不返回 n，而是返回 1，就会导致错误。例如，F(0) 的结果应该是 1。但实际上，它应该返回 0。

接下来，我们得到公式。如果 n 不是 0 或 1，我们该怎么办？我们计算 F(n - 1) + F(n - 2)。最后，我们要将所有数字合并在一起得到最终结果。我们使用加法来实现。

这是斐波那契数列的正式定义。通常，递归函数用于描述分治算法的运行时间。我和我的算法教授都认为，这实际上是创建分治算法的好工具。

def F(n):
  if n == 0 or n == 1:
    return n
  else:
    return F(n-1)+F(n-2)

有了分而治之的知识，上述代码更加清晰，更易于阅读。

我们经常使用执行树来计算递归的结果。计算机霸主🤖不需要这样做，但这对人类来说很有用，可以让他们了解分治算法是如何运作的。对于 F(4) 来说，它看起来像这样：

n 为 4，且 n 大于 0 或 1。因此，我们执行 f(n-1) + f(n-2)。我们暂时忽略加法运算。结果会产生两个新节点，分别是 3 和 2。3 大于 0 或 1，因此我们也执行相同的操作。2 也一样。我们重复此操作，直到得到一堆非 0 非 1 的节点。然后，我们将所有节点相加。1 + 1 + 0 + 0 + 1 = 3，这就是正确答案。

结论📕

一旦确定了如何将问题分解为多个较小的部分，就可以使用并发编程同时执行这些部分（在不同的线程上），从而加快整个算法的速度。

分治算法是提高算法速度最快、最简单的方法之一，在日常编程中非常有用。以下是我们在本文中讨论的最重要的主题：

• 什么是分而治之？
• 递归
• 归并排序
• 河内塔
• 编写分治算法
• 复发
• 斐波那契数列

下一步是探索多线程。选择你选择的编程语言，然后在谷歌上搜索“Python 多线程”作为示例。弄清楚它的工作原理，看看你是否可以从这个新角度解决你自己代码中的任何问题。

你还可以学习如何求解递归（找出递归的渐近运行时间），这是我即将撰写的下一篇文章。如果你不想错过，或者喜欢这篇文章，不妨考虑订阅我的邮件列表😁✨

动态规划

动态规划（DP）将优化问题分解为更小的子问题，并存储每个子问题的解决方案，以便每个子问题只解决一次。

它既是一种数学优化方法，也是一种计算机编程方法。

优化问题寻求的是最大或最小解。动态规划通常用于解决优化问题。一般规则是，如果遇到一个问题，初始算法可以在 2n 的时间内解决^，那么使用动态规划 (DP) 可能更适合。

动态规划为什么叫动态规划？

理查德·贝尔曼 (Richard Bellman)在 20 世纪 50 年代发明了动态规划 (DP)。贝尔曼将其命名为动态规划，因为当时他的雇主兰德公司 (RAND) 不喜欢数学研究，也不愿资助此类研究。他之所以命名为动态规划，是为了掩盖他实际上从事数学研究的事实。

贝尔曼在他的自传《飓风之眼：自传》（1984 年，第 159 页）中解释了动态规划这一术语背后的原因。他解释道：

我在兰德公司度过了1950年的秋季学期。我的首要任务是为多阶段决策过程起个名字。一个有趣的问题是，动态规划这个名字是怎么来的？20世纪50年代对数学研究来说并非好年景。当时华盛顿有一位非常有趣的先生，名叫威尔逊。他是国防部长，他对“研究”这个词有着病态的恐惧和憎恨。我使用这个词并非轻描淡写，而是用得恰如其分。如果有人在他面前提到“研究”这个词，他的脸就会涨红，甚至会变得暴躁。你可以想象他对“数学”这个词的感受。兰德公司受雇于空军，而威尔逊实际上是空军的老板。因此，我觉得我必须做点什么，让威尔逊和空军不了解我在兰德公司内部从事数学工作的事实。我该选什么头衔，什么名字呢？首先，我对规划、决策和思考很感兴趣。但“规划”这个词，对于……来说，并不是一个合适的词。原因有很多。因此，我决定使用“编程”这个词。我想表达的是，它是动态的、多阶段的、随时间变化的。我想，一举两得。我们来用一个词，它在经典物理意义上有着绝对精确的含义，也就是“动态”。它作为形容词还有一个非常有趣的特性，那就是“动态”这个词不可能带有贬义。试想一下，有什么组合可能会赋予它贬义的含义？根本不可能。所以，我觉得“动态规划”是个好名字。即使是国会议员也不会反对。所以我用它作为我活动的统称。

什么是子问题？

子问题是原始问题的较小版本。我们来看一个例子。使用以下等式：

1 + 2 + 3 + 4

我们可以将其分解为：

1 + 2

3 + 4

一旦我们解决了这两个较小的问题，我们就可以将这些问题的解决方案相加以找到整体问题的解决方案。

注意这个子问题如何将原始问题分解成构成解决方案的各个部分。虽然这只是一个小例子，但它很好地展现了动态规划的美妙之处。如果我们将问题扩展为数百个数字的加法，就更清楚地明白为什么我们需要动态规划了。请看这个例子：

6 + 5 + 3 + 3 + 2 + 4 + 6 + 5

我们有两次 6 + 5 的计算结果。第一次计算时，我们算出了 6 + 5 的数值。第二次计算时，我们心里想：

“啊，6 + 5。我以前见过这个。结果是 11！”

在动态规划中，我们将问题的解存储在内存中，这样就无需重新计算。通过找到每个子问题的解，我们就可以解决原始问题本身。

存储解决方案的行为称为记忆化。

动态规划中的记忆法是什么？

首先，让我们看看为什么存储解的答案是有意义的。我们将研究一个著名的分治问题——斐波那契数列。分治法是一种动态规划，但不存储解。

需要分而治之的主要部分有 3 个：

1. 将问题分解为同一类型的较小子问题。
2. 征服——递归地解决子问题。
3. 合并——合并所有子问题以创建原始问题的解决方案。

动态规划在步骤 2 中添加了一个额外的步骤。这就是记忆。

斐波那契数列是一个数字序列。它等于最后一个数字 + 当前数字。我们从 1 开始。

1 + 0 = 1

1 + 1 = 2

2 + 1 = 3

3 + 2 = 5

5 + 3 = 8

在 Python 中，通常这样编程：

def F(n):
  if n == 0 or n == 1:
    return n
  else:
return F(n-1)+F(n-2)

如果您不熟悉递归，我为您写了一篇博客文章，您应该先阅读。

让我们计算一下 F(4)。在执行树中，它看起来像这样：

我们计算了两次 F(2)。这可能是一个小例子，但对于更大的输入（例如 F(10)），重复次数就会增加。动态规划的目的是避免重复计算同一个值。

我们不需要计算两次 F(2)，而是将解存储在某个地方并只计算一次。

我们将把解存储在一个数组中。F(2) = 1。这样，我们的数组看起来就像 memo[2] = 1。下面是一些使用动态规划计算斐波那契数列的 Python 代码。

def fibonacciVal(n):
    memo[0], memo[1] = 0, 1
    for i in range(2, n+1):
        memo[i] = memo[i-1] + memo[i-2]
    return memo[n]

这里列出的示例都是用 Python 编写的。我会尽力确保代码的通用性。这意味着，如果你想用 Java 编写代码，转换过来应该不会太难。

如何识别动态规划问题

理论上，每个问题都可以动态解决。那么问题是：

“我应该什么时候用动态规划来解决这个问题？”

对于那些处于可处理问题和难处理问题之间的问题，我们应该使用动态规划。

可处理问题是那些可以在多项式时间内解决的问题。这只是一种花哨的说法，意思是我们可以快速解决它。二分查找和排序都很快。难处理问题是那些运行时间呈指数级增长的问题。它们很慢。一般来说，难处理问题是那些只能通过暴力破解每个组合（ NP难）才能解决的问题。

当我们看到这样的术语时：

“最短/最长、最小化/最大化、最少/最多、最少/最多、最大/最小”

我们知道这是一个优化问题。

DP 算法的另一个优点是，它们的正确性证明通常是不证自明的。其他算法策略通常更难证明其正确性，因此更容易出错。

例如，贪婪算法在概念上可能看起来更简单，并且通常运行速度更快，但它们的正确性却很难证明，因为它们需要对输入的结构做出许多隐含的假设。

当我们看到这类术语时，问题可能要求一个具体的数字（“求编辑操作的最小次数”），也可能要求一个结果（“求最长公共子序列”）。后一种问题很难被识别为动态规划问题。如果某个问题听起来像优化，那么它可以通过动态规划来解决。

现在，假设我们发现了一个优化问题，但不确定能否用动态规划 (DP) 解决。首先，确定优化的目标。一旦我们意识到优化的目标，就必须确定执行该优化的难易程度。有时，贪婪方法足以找到最优解。

动态规划采用蛮力方法。它识别重复的工作，并消除重复。

在开始将问题转化为动态规划问题之前，我们会先思考一下暴力破解的解法可能是什么样子。暴力破解解法中可能存在重复的子步骤吗？如果存在，我们尝试将问题转化为动态规划问题。

掌握动态规划的关键在于理解问题。列出所有可能影响答案的输入。确定所有输入和输出后，尝试确定问题是否可以分解为子问题。如果能够识别子问题，我们或许可以使用动态规划。

列出所有影响答案的输入，稍后再考虑缩减该集合的大小。一旦确定了输入和输出，我们就会尝试确定问题是否可以分解为更小的子问题。如果我们能够确定更小的子问题，那么我们就可以应用动态规划来解决问题。然后，找出递归式并求解。在尝试找出递归式时，请记住，我们编写的任何递归式都必须能够帮助我们找到答案。有时答案就是递归式的结果，有时我们需要通过查看递归式中的几个结果来获得结果。

一个问题可以用动态规划解决，并不意味着没有更有效的解决方案。用动态规划解决问题感觉就像变魔术一样，但请记住，动态规划只是一种巧妙的蛮力。有时它能带来丰厚的回报，有时却收效甚微。

如何使用动态规划解决问题

现在我们已经了解了动态规划是什么以及它通常的工作原理，接下来我们来看看如何创建一个动态规划解决方案。我们将使用加权区间调度问题来探索动态规划的流程。

假设你是一家干洗店的老板。有n 位顾客来给你洗衣服。你每次只能清洗一位顾客的一堆衣服（PoC）。每堆衣服i必须在某个预定的开始时间 s_i 和某个预定的结束时间 f_i 进行清洗。

每堆衣服都有一个关联值 v_i，取决于它对您的业务的重要性。例如，有些顾客可能会支付更多费用以加快衣服清洗速度。或者有些顾客可能是回头客，您希望他们感到满意。

作为这家干洗店的老板，你必须确定一个最优的衣物处理计划，使当天的总价值最大化。这个问题是加权区间调度问题的重新表述。

现在你将看到解决动态规划问题的 4 个步骤。有时，你可以跳过某个步骤。有时，你的问题已经明确定义，你无需担心前几个步骤。

步骤 1. 写出问题

拿一张纸。写下问题。具体来说：

• 问题是什么？
• 有哪些子问题？
• 解决方案大致是什么样的？

在干洗店问题中，我们把子问题用文字表达出来。我们想要确定的是每堆衣服按开始时间排序后，其最大价值安排。

为什么要按开始时间排序？好问题！我们想跟踪当前正在运行的进程。如果按结束时间排序，我们脑子里想的就不太对劲了。我们可能有两个进程的结束时间相似，但开始时间却完全不同。时间是线性流动的。如果我们有一堆衣服从下午 1 点开始，我们知道这一点。但如果有一堆衣服在下午 3 点结束，那就像是倒着看一样。不太合理。

我们可以找到从 n-1 到 n 的桩的最大值调度方案。然后是 n - 2 到 n 的桩的最大值调度方案，以此类推。通过找到每个子问题的解，我们就可以解决原始问题本身。从 1 到n 的桩的最大值调度方案。由于子问题是原始问题的缩小版本，因此可以使用子问题来解决原始问题。

对于区间调度问题，我们唯一的解决方法是强行求解所有子集，直到找到最优解。我们所说的强行求解不是逐个子集，而是将其分解。先从 n-1 强行求解到 n，然后再对 n-2 强行求解到 n。最终，我们会得到许多可以动态求解的小问题。我们希望构建子问题的解决方案，使每个子问题都建立在先前的问题之上。

2. 数学递归

我知道，数学很烂。如果你能听我解释，你会发现这并不难。数学递归的用途是：

定义分治法（动态规划）技术的运行时间

但是，我跟你说，它们也可以用来定义一个问题。如果你的子问题很难转化为数学，那么它可能就是错误的子问题。

创建数学递归有两个步骤：

1：定义基准案例

基本情况是问题的最小可能形式。

创建重复时，请问自己以下问题：

“我在第 0 步做出什么决定？”

不一定非得是 0。基准情况是问题可能的最小分母。我们在斐波那契数列中见过这种情况。基准是：

• 如果 n == 0 或 n == 1，则返回 1

知道基准情况在哪里很重要，这样我们才能创建递归。在我们的问题中，我们需要做出一个决定：

• 把那堆衣服放上去洗

或者

• 今天不要洗那堆衣服

如果 n 为 0，即 PoC 为 0，则不执行任何操作。我们的基准情况如下：

如果 n == 0，则返回 0

2：我在步骤 n 做出什么决定？

现在我们知道了基准情况，如果我们到了步骤 n，我们该怎么做？对于目前符合计划的每一堆衣服（兼容意味着开始时间晚于当前正在洗涤的这堆衣服的完成时间），算法会选择两个选项。

现在我们知道了基准情况会发生什么，以及其他情况。接下来我们需要找出算法需要哪些信息来向前或向后推算。

“如果我的算法处于步骤 i，那么它需要什么信息来决定在步骤 i+1 中做什么？”

为了在两个选项之间做出选择，算法需要知道下一个兼容的 PoC（一堆衣服）。对于给定的一堆衣服 p，下一个兼容的 PoC 是 PoC n，并且 s_n（PoC n 的开始时间）发生在 f_p（PoC p 的结束时间）之后。s_n 和 f_p 之间的差异应该最小化。

用英语来说，假设我们有一台洗衣机。我们在 13:00 放了一堆衣服进去。下一堆衣服会在 13:01 开始洗。我们不能直接打开洗衣机把衣服放进去。下一堆兼容的衣服是在当前正在洗的衣服完成时间之后开始洗的。

“如果我的算法处于步骤 i，那么它需要什么信息来决定在步骤 i-1 中做什么？”

算法需要了解未来的决策。这些决策针对 PoC i到n做出，以决定是否运行 PoC i-1。

现在我们已经回答了这些问题，或许我们已经开始在脑海中形成一个循环的数学决策了。如果没有，也没关系，随着我们接触到更多问题，写出递归公式会变得更容易。

这是我们的重复：

让我们详细探究一下这种数学递归的原理。OPT(i) 表示 PoC i到n 的最大值调度，其中 PoC 按开始时间排序。OPT(i) 是我们之前的子问题。

我们从起始条件开始。所有递归都需要在某个地方停止。如果我们调用 OPT(0)，返回值将为 0。

为了确定 OPT(i) 的值，我们考虑两个选项。我们希望从中选择最大值来实现我们的目标。我们的目标是找到所有衣物堆的最大价值方案。一旦我们选择了在步骤 i 中给出最大结果的选项，我们就将其值记录为 OPT(i)。

运行或不运行 PoC i 这两个选项在数学上表示如下：

v_i + OPT(下一个[n])

这代表着运行 PoC i 的决定。它将 PoC i 获得的值添加到 OPT(next[n]) 中，其中 next[n] 表示 PoC i 之后的下一堆兼容的衣物。将这两个值相加，我们得到了从 i 到 n 的最大值调度方案，这样，如果运行了 i，这些方案将按开始时间排序。

这里按开始时间排序是因为 next[n] 是紧接着 v_i 之后的，所以默认情况下，它们是按开始时间排序的。

OPT(i + 1)

如果我们决定不运行i，那么我们的值就是 OPT(i + 1)。该值不会增加。OPT(i + 1) 给出了 i+1 到 n 的最大值调度方案，并按开始时间排序。

3. 确定记忆数组的维度及其填充方向

我们的DP问题的解是OPT(1)。我们可以将其写成PoC 1到n的最大值调度方案，其中PoC按开始时间排序。这与“PoC i到n的最大值调度方案”相呼应。我们的解可以写成OPT(1)。

从步骤 2 开始：

回到之前的斐波那契数列，我们的动态规划解法依赖于这样一个事实：从 0 到 n - 1 的斐波那契数列已经被记住了。也就是说，为了求 F(5)，我们已经记住了 F(0)、F(1)、F(2)、F(3)、F(4)。我们想在这里做同样的事情。

我们面临的问题是如何填写记忆表。在调度问题中，我们知道 OPT(1) 依赖于 OPT(2) 和 OPT(next[1]) 的解。由于排序的原因，PoC 2 和 next[1] 的开始时间晚于 PoC 1。我们需要将记忆表从 OPT(n) 填充到 OPT(1)。

我们可以清楚地看到，我们的数组是一维的，从 1 到 n。但是，如果我们看不清楚，我们可以用另一种方法计算。数组的维数等于 OPT(x) 所依赖的变量的数量和大小。在我们的算法中，我们有 OPT(i) - 一个变量 i。这意味着我们的数组将是一维的，其大小为 n，因为有 n 堆衣服。

如果我们知道n = 5，那么我们的记忆数组可能看起来像这样：

备注 = [0, OPT(1), OPT(2), OPT(3), OPT(4), OPT(5)]

0 也是基本情况。根据我们之前的递归，memo[0] = 0。

4.编写解决方案

就我个人而言，当我编写动态规划解决方案时，我喜欢阅读递归式并尝试重新创建它。我们的第一步是将数组初始化为 (n + 1) 的大小。在 Python 中，我们不需要这样做。但如果你使用其他语言，你可能需要这样做。

我们的第二步是设定基准情况。

要计算包含 job[i] 的利润，我们需要找到与 job[i] 不冲突的最新任务。思路是使用二分查找法来查找最新的非冲突任务。我从这里复制了代码，但略作修改。

首先，我们来定义一下什么是“作业”。正如我们所见，一项作业由三部分组成：

# Class to represent a job 
class Job: 
    def __init__ (self, start, finish, profit): 
        self.start = start 
        self.finish = finish 
        self.profit = profit 

开始时间、结束时间以及运行该作业的总利润（收益）。

我们下一步要规划的是时间表。

# The main function that returns the maximum possible 
# profit from given array of jobs
def schedule(job): 
    # Sort jobs according to start time 
    job = sorted(job, key = lambda j: j.start) 

    # Create an array to store solutions of subproblems. table[i] 
    # stores the profit for jobs till arr[i] (including arr[i]) 
    n = len(job) 
    table = [0 for _ in range(n)] 

    table[0] = job[0].profit;

之前我们了解到，表格是一维的。我们按开始时间对作业进行排序，创建这个空表，并将 table[0] 设置为 job[0] 的利润。由于我们已经按开始时间排序，因此第一个兼容的作业始终是 job[0]。

下一步，我们用之前学过的递归算法来填充条目。为了找到下一个合适的工作，我们使用二分查找。稍后发布的完整代码会包含这个功能。现在，我们先来理解一下算法。

如果下一个兼容作业返回 -1，则表示索引 i 之前的所有作业都与其冲突（因此无法使用）。inclprof 表示我们将该项目包含在最大值集合中。然后，我们将其存储在 table[i] 中，以便以后再次使用此计算。

    # Fill entries in table[] using recursive property 
    for i in range(1, n): 

        # Find profit including the current job 
        inclProf = job[i].profit 
        l = binarySearch(job, i) 
        if (l != -1): 
            inclProf += table[l]; 

        # Store maximum of including and excluding 
        table[i] = max(inclProf, table[i - 1]) 

我们的最后一步是返回所有项目的利润，最多 n-1。

    return table[n-1] 

完整代码如下：

# Python program for weighted job scheduling using Dynamic 
# Programming and Binary Search 

# Class to represent a job 
class Job: 
    def __init__ (self, start, finish, profit): 
        self.start = start 
        self.finish = finish 
        self.profit = profit 

# A Binary Search based function to find the latest job 
# (before current job) that doesn't conflict with current 
# job. "index" is index of the current job. This function 
# returns -1 if all jobs before index conflict with it. 
def binarySearch(job, start_index): 
    # https://en.wikipedia.org/wiki/Binary_search_algorithm

    # Initialize 'lo' and 'hi' for Binary Search 
    lo = 0
    hi = start_index - 1

    # Perform binary Search iteratively 
    while lo <= hi: 
        mid = (lo + hi) // 2
        if job[mid].finish <= job[start_index].start: 
            if job[mid + 1].finish <= job[start_index].start: 
                lo = mid + 1
            else: 
                return mid 
        else: 
            hi = mid - 1
    return -1

# The main function that returns the maximum possible 
# profit from given array of jobs 
def schedule(job): 
    # Sort jobs according to start time 
    job = sorted(job, key = lambda j: j.start) 

    # Create an array to store solutions of subproblems. table[i] 
    # stores the profit for jobs till arr[i] (including arr[i]) 
    n = len(job) 
    table = [0 for _ in range(n)] 

    table[0] = job[0].profit; 

    # Fill entries in table[] using recursive property 
    for i in range(1, n): 

        # Find profit including the current job 
        inclProf = job[i].profit 
        l = binarySearch(job, i) 
        if (l != -1): 
            inclProf += table[l]; 

        # Store maximum of including and excluding 
        table[i] = max(inclProf, table[i - 1]) 

    return table[n-1] 

# Driver code to test above function 
job = [Job(1, 2, 50), Job(3, 5, 20), 
    Job(6, 19, 100), Job(2, 100, 200)] 
print("Optimal profit is"), 
print(schedule(job))

恭喜！🥳 我们刚刚写出了第一个动态程序！既然我们已经入门了，让我们来研究一下另一种类型的动态规划问题。

背包问题

想象一下你是个罪犯。你真是个狡猾的家伙。你闯进了比尔·盖茨的豪宅。哇，好吗！？！这到底有几个房间？他的洗衣机房比我整栋房子都大？？？好了，别再分心了。你带了一个小包。一个背包——如果你愿意的话。

包里只能装这么多东西。我们随便给它一个数字。这个包能承受15的重量，但不能再多了。我们的目标是最大化我们的收入，b。

贪婪法是选择价值最高且能放进袋子里的物品。我们试试看。我们要偷比尔·盖茨的电视。4000英镑？不错。但他的电视只有15英镑。所以……我们带着4000英镑走了。

比尔·盖茨有很多手表。假设他有两块手表，每块重5英镑，价值2250英镑。如果我们把两块都偷走，就能得到4500英镑，重量是10英镑。

在贪婪算法中，我们不会优先选择这些手表。但对人类来说，选择价值更高、体积更小的物品是合理的。贪婪算法无法最优地解决 {0,1} 背包问题。{0, 1} 意味着我们要么取走整个物品 {1}，要么不取 {0}。然而，动态规划可以最优地解决 {0, 1} 背包问题。

解决这个问题的简单方法是考虑所有物品的所有子集。对于比尔·盖茨的每一种物品组合，我们计算该组合的总重量和总价值。

我们只考虑权重小于 W_max 的组合。然后，我们选取​​权重最高的组合。这简直是一场灾难！这得花多长时间？比尔·盖茨早就回家了，你甚至还没走到三分之一的路程！用大 O 表示，这个算法的时间复杂度为 O(n^2)。

您可以看到，我们已经对解决方案和问题有一个大致的了解，而无需用数学形式将其写下来！

数学

想象一下，我们手里有比尔·盖茨家里所有物品的清单。也许我们从保险单上偷来的。现在，想想未来。这个问题的最佳解决方案是什么？

我们有一个子集 L，它是最优解。L 是 S 的子集，而 S 包含了比尔·盖茨的所有东西。

我们随机选择一个物品 N。L 要么包含 N，要么不包含。如果 L 不使用 N，则该问题的最优解与 {1, 2, ..., N-1} 相同。这里假设比尔·盖茨的物品按价值/重量排序。

假设原始问题的最优解不是子问题的最优解。如果我们对较小的问题有子最优解，那么就会出现矛盾——我们应该对整个问题有最优解。

如果 L 包含 N，那么该问题的最优解与 {1, 2, 3, ..., N-1} 相同。我们知道该物品在 L 中，因此 L 已经包含 N。为了完成计算，我们重点关注剩余的物品。我们找到剩余物品的最优解。

但是，我们现在有了新的最大允许重量 W_max - W_n。如果解决方案中包含物品 N，则总重量现在是减去物品 N（该物品已经在背包中）后的最大重量。

这是两种情况。要么项目 N 是最优解，要么不是。

如果项目 N 的权重大于 W_max，则不能将其包括在内，因此情况 1 是唯一的可能性。

为了更精确地定义这个递归解，令 S_k = {1, 2, ..., k} 和 S_0 = ∅

令 B[k, w] 为使用 S_k 子集获得的最大总收益。总权重最多为 w。

然后我们为每个 w ≤ W_max 定义 B[0, w] = 0，并且：

我们想要的解决方案是 B[n, W_max]。

背包问题的制表

好吧，拿出纸笔来。不，真的。事情很快就会变得混乱。这个记忆表是二维的。我们有这些项目：

(1, 1), (3, 4), (4, 5), (5, 7)

元组在哪里(weight, value)。

我们有两个变量，所以我们的数组是二维的。第一维是从 0 到 7。第二维是值。

我们希望权重为 7，以获得最大收益。

权重是 7。我们从 0 开始计数（这不是动态规划的玩意儿，只是编程的习惯）。我们把每个元组放在左边。好了。现在开始填写表格！

这些列代表权重。权重为 0 时，总权重为 0。权重为 1 时，总权重为 1。我知道这很明显。但这是一个重要的区别，以后会用到。

当我们的体重为0时，无论如何都无法携带任何东西。所有物体的重量之和为0。

如果我们的总权重为 1，那么我们能取的最佳项是 (1, 1)。随着我们向下遍历这个数组，我们可以取更多的项。在 (4, 3) 行，我们可以取 (1, 1) 或 (4, 3)。但目前，我们只能取 (1, 1)。那么这一行的最大收益就是 1。

如果总权重为 2，那么我们能做的最好的选择就是 1。每种物品只有 1 件。我们不能重复物品。所以，无论我们在第一行的哪个位置，我们能做的绝对最佳选择就是 (1, 1)。

现在让我们开始使用 (4, 3)。如果总重量为 1，但 (4, 3) 的重量为 3，那么在重量至少为 3 之前，我们还不能取走该物品。

现在我们的权重是 3。让我们比较一下。我们想取以下最大值：

MAX(4 + T[0][0], 1)

如果我们位于 2, 3，我们可以取最后一行的值，或者使用该行的项目。我们向上一行，然后倒数 3（因为该项目的权重为 3）。

实际上，公式是减去该行商品的重量后剩余的重量。(4, 3) 的重量是 3，我们现在的重量是 3。3 - 3 = 0。因此，我们现在位于 T[0][0]。T[上一行的编号][当前总重量 - 商品重量]。

MAX(4 + T[0][0], 1)

1 是因为前一项。此处最大值为 4。

最大（4 + t[0][1]，1）

总重量为 4，项目重量为 3。4 - 3 = 1。上一行是 0。t[0][1]。

这一行剩下的内容就不烦你了，因为没什么特别的。我们一共有 2 件物品，而且我们已经用它们凑成了 5 件。由于没有新物品，所以最大值是 5。

下一行：

这里有一个小秘密。我们的元组是按重量排序的！这意味着我们可以把前几行的数据填到下一个重量点。我们知道 4 已经是最大值了，所以我们可以直接填上去。这就是 memoisation 发挥作用的地方！我们已经有数据了，何必再重新计算呢？

我们往上走一排，然后往后退4步。这样我们就得到了：

最大（4 + T[2][0]，5）。

现在我们计算总重量5。

最大（5 + T[2][1]，5）= 6

我们再做同样的事情：

最大（5 + T[2][2]，5）= 6

现在我们的总重量为 7。我们选择以下最大值：

最大值（5 + T[2][3], 5）= 最大值（5 + 4, 5）= 9

如果总重量为 7，且有 3 件物品（1, 1）、（4, 3）、（5, 4），那么我们能得到的最好结果就是 9。

由于我们的新物品的重量从 5 开始，因此我们可以从上一行复制，直到重量达到 5。

然后我们再做一次最大值。

总重量 - 新项目的重量。总重量为 5 - 5 = 0。我们希望上一行位于位置 0。

最大（7 + T[3][0]，6）

6 来自于上一行中该总重量中的最佳值。

最大（7 + 0，6）= 7

最大（7 + T[3][1], 6）= 8

最大（7 + T[3][2]，9）= 9

9 是我们从一组物品中挑选物品时所能得到的最大值，使得总重量小于等于 7。

使用动态规划寻找 {0, 1} 背包问题的最优集

现在，我们究竟要选择哪些物品来组成最优集合呢？我们从以下物品开始：

我们想知道 9 是从哪里来的。它来自顶部，因为第四行 9 正上方的数字是 9。由于它来自顶部，所以 (7, 5) 项没有被用在最优集合中。

这个9从哪里来的？

这个 9 不是来自它上面的行。项 (5, 4) 一定在最优集合中。

我们现在向上移动一行，然后后退 4 步。之所以后退 4 步，是因为项目 (5, 4) 的重量为 4。

4 不是来自上一行。项 (4, 3) 必定在最优集合中。

物品 (4, 3) 的权重为 3。我们向上走 3 步，然后后退 3 步，得到：

一旦权重达到 0，我们就完成了。我们选中的两个商品是 (5, 4) 和 (4, 3)。总权重为 7，总收益为 9。我们只需将两个元组相加即可得出结果。

让我们开始编写代码。

编码

现在我们知道了它的工作原理，也推导出了它的递归式——编写代码应该不难。假设我们的二维数组是 i（行）和 j（列），那么我们有：

if j < wt[i]:

如果我们的权重 j 小于项目 i 的权重（i 对 j 没有贡献）那么：

if j < wt[i]:
    T[i][j] = T[i - 1][j]
else:
    // weight of i >= j
    T[i][j] = max(val[i] + t[i - 1][j-wt(i), t[i-1][j])
    // previous row, subtracting the weight of the item from the total weight or without including ths item

这就是程序的核心功能。我从这里复制了一些代码来帮助解释这一点。我不会对这段代码进行过多的解释，因为它除了我已经解释过的内容之外，并没有太多其他内容。如果您对此感到困惑，请在下方留言（可以匿名留言）或给我发邮件 😁

# Returns the maximum value that can be put in a knapsack of 
# capacity W 
def knapSack(W , wt , val , n): 

    # Base Case 
    if n == 0 or W == 0: 
        return 0

    # If weight of the nth item is more than Knapsack of capacity 
    # W, then this item cannot be included in the optimal solution 
    if (wt[n-1] > W): 
        return knapSack(W , wt , val , n-1) 

    # return the maximum of two cases: 
    # (1) nth item included 
    # (2) not included 
    else: 
        return max(val[n-1] + knapSack(W-wt[n-1] , wt , val , n-1), 
                   knapSack(W , wt , val , n-1)) 


# To test above function 
val = [60, 100, 120] 
wt = [10, 20, 30] 
W = 50
n = len(val) 
print(knapSack(W , wt , val , n))
# output 220

动态规划问题的时间复杂度

在DP中，时间复杂度计算如下：

唯一状态数 * 每个状态所花费的时间

对于我们最初的问题，即加权区间调度问题，我们有 n 堆衣服。每堆衣服的调度都在常数时间内完成。时间复杂度为：

O(n) + O(1) = O(n)

如果您想了解更多有关时间复杂性的信息，我写了一篇有关 Big O 符号的文章。

我们的背包问题有 n 个物品。表格会根据背包的总容量而增长，时间复杂度为：

O(nw)

其中 n 是物品数量，w 是背包容量。

我要告诉你一个小秘密。我们可以通过一个算法的递归式推导出它的时间复杂度。你可以使用一个叫做“主定理”的东西来解决这个问题。这个定理的概要如下：

现在，我得说实话了。大师级的Therom值得专门写一篇博文来介绍。目前为止，我觉得这个视频很棒：

动态规划 vs 分治 vs 贪婪

动态规划与分治法非常相似。动态规划基于分治法，只不过我们会记住结果。

贪婪算法则有所不同。它的目标是通过做出当时最佳的选择来进行优化。有时，这并不能优化整个问题。以这个问题为例。我们有3枚硬币：

1便士、15便士、25便士

有人想找零 30 便士。贪婪算法会选择 25 便士，然后再选择 5 * 1 便士，总共 6 枚硬币。最优解是 2 * 15 便士。贪婪算法从大到小排序。在 25 的位置，最佳选择是选择 25 便士。

制表（自下而上） vs 记忆（自上而下）

动态规划有两种类型：制表法和记忆法。

记忆法（自上而下）

我们已经计算了所有子问题，但不知道最优求值顺序。然后，我们会从根节点开始递归调用，希望能够接近最优解，或者获得最终能够得到最优解的证明。记忆化机制可以确保永远不需要重新计算子问题，因为我们会缓存结果，从而避免重复计算重复的子树。

从我们之前的斐波那契数列来看，我们从根节点开始。子树 F(2) 不会被计算两次。

它从树的顶部开始，从叶子/子树向上计算子问题，直至根部。记忆化是一种自上而下的方法。

制表（自下而上）

我们还见过动态规划被用作“填表”算法。通常，这种表是多维的。这类似于记忆化，但有一个主要区别。我们必须选择进行计算的确切顺序。我们看到的背包问题，是从左到右、从上到下填充表格的。我们知道填充表格的确切顺序。

有时，“表格”并不像我们见过的表格。它可能是更复杂的结构，例如树形结构。或者特定于问题领域，例如地图上飞行距离内的城市。

制表与备忘录 - 优点和缺点

一般来说，记忆法比制表法更容易编写。我们可以编写一个“记忆器”包装函数，自动完成记忆。而制表法则需要我们自己确定一个排序。

记忆化机制存在内存问题。如果我们计算的是 F(10^8) 这样的大数，每次计算都会延迟，因为我们必须将结果放入数组中。而且数组的大小会迅速增长。

如果我们访问子问题的顺序（或尝试访问的顺序）并非最优，那么这两种方法都可能不是时间最优的，尤其是在计算子问题的方法不止一种的情况下（通常缓存可以解决这个问题，但理论上在某些特殊情况下缓存可能无法解决这个问题）。记忆化通常会将时间复杂度添加到空间复杂度中（例如，使用制表法，我们可以更自由地舍弃计算，例如，使用 Fib 的制表法可以使用 O(1) 的空间复杂度，但使用 Fib 的记忆化则需要 O(N) 的堆栈空间）。

结论

你在动态规划中遇到的大多数问题都已经以某种形式存在。通常，你的问题会基于之前问题的答案。以下列出了一些使用动态规划的常见问题。

我希望大家在遇到问题的时候，能先思考一下“这个问题能用DP解决吗？”，然后尝试一下。