什么是动态规划（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解决吗？”，然后尝试一下。