动态编程教程：用 Python 制作高效的程序

什么是动态规划？

动态规划是一种解决问题的技术，用于通过将复杂问题递归分解为子问题来解决，然后每个子问题单独解决。动态编程优化了递归规划，节省了我们以后重新计算输入的时间。

这与分而治之技术的不同之处在于，动态规划解决方案中的子问题是重叠的，因此解决一个子问题所需的一些相同步骤对于其他子问题也需要。

这就引出了动态规划的主要优势。动态编程允许我们第一次简单地存储每个步骤的结果，并在以后每次重复使用它，而不是重新计算这些共享步骤。

注意：
动态规划是较大类别递归规划的特例，但并非所有递归情况都可以使用动态规划

为什么动态规划是有效的？递归与 DP

如果两者如此紧密地交织在一起，为什么只要有可能，动态规划就会受到青睐呢？这是因为暴力递归程序在面对重叠步骤时经常重复工作，在此过程中花费不必要的时间和资源。

动态编程通过确保每个相同的步骤只完成一次来解决此问题，并将该步骤的结果存储在收集器（如哈希表或数组）中，以便在再次需要时调用。这样，动态编程可以减少重复工作，从而提高运行时效率。

注意：
动态规划本质上是用空间效率换取时间效率，因为解决方案存储需要暴力递归解决方案中未使用的空间。

动态规划示例

真实世界的动态编程

与计算机不同，动态编程等基于内存的过程对人类来说是直观的。

考虑这个真实世界的例子：

想象一下，你想去几条街外的一家新杂货店，但你不知道怎么去那里。为了解决通往商店的路线的子问题，您可以在智能手机的地图上查找路线，然后前往那里。

如果你以递归的方式思考，每次你想去商店时，你都必须花时间再次查找方向。

相反，我们自然而然地动态思考，记住我们第一次查找商店时的路线。因此，我们将来去时不需要花时间查找它们。

从本质上讲，这也是动态编程在程序中的功能。

阶乘问题

我们可以在现实生活中看到动态编程如何比递归更有效，但让我们看看它与 Python 代码的实际应用！

下面我们有两个解决方案，它们都找到给定输入的斐波那契数，然后显示程序运行时的图形。一种是简单的暴力递归，另一种是使用动态编程。

看看区别：

动态规划：

import time
import matplotlib.pyplot as plt

calculated = {}

def fib(n):
  if n == 0: # base case 1
    return 0
  if n == 1: # base case 2
    return 1
  elif n in calculated:
    return calculated[n]
  else: # recursive step
    calculated[n] = fib(n-1) + fib(n-2)
    return calculated[n]

showNumbers = False
numbers = 20

递归：

import time
import matplotlib.pyplot as plt

def fib(n):
  if n <= 0: # base case 1
    return 0
  if n <= 1: # base case 2
    return 1
  else: # recursive step
    return fib(n-1) + fib(n-2)

numbers = 20

如您所见，在动态解决方案的代码中，我们添加了在进入下一个递归步骤（第 13 – 15 行）之前存储旧结果（第 12 行）的功能。我们将在本文后面看到更复杂的动态解决方案及其分步分解。

自下而上的动态规划

并非所有动态解决方案都以相同的方式工作。有些是自下而上构建的，而另一些则是自上而下构建的。区别在于每个问题如何开始以及如何存储子问题结果。

自下而上的动态规划解决方案首先查看尽可能小的子问题（称为基本情况），然后逐步解决每个子问题。当每个子问题被解决时，其解决方案将被保存并用于解决下一个最低的子问题。最后，这些建筑解决方案将导致主要问题的答案。

什么是制表？

制表是按顺序存储来自自下而上方法的子问题结果的过程。

在制表中，我们不会挑选需要解决的子问题，而是解决基本情况和主要问题之间的每个子问题。这种顺序使制表允许使用列表或数组，因为这些集合按特定顺序组织信息。

注意：
制表是迭代的，而不是递归的，因为在制表中，我们在开始下一个子问题之前完成每个子问题。

自上而下的动规划

自上而下的动态规划与自下而上的相反。自上而下的解决方案首先查看主要问题，并将其分解为越来越小的必要支持问题，直到达到基本情况。这是构建递归解决方案的最常见方法。

在使用这种递归链时，自上而下的动态规划只在需要时解决子问题，而不是按顺序解决所有问题。

什么是记忆？

记忆是以自上而下的方法存储子问题结果的过程。

由于自上而下的方法根据需要解决问题，因此记忆必须以非顺序方式存储数据。这意味着哈希表是最好的集合类型，因为它们以无序方式存储数据。

在 Python 中，最好使用字典数据结构来实现这一点，因为我们可以使用它来存储具有键/值对的无序数据。

动态编程示例：自下而上与自上而下

为了更好地理解这些设计之间的差异，让我们看看如何以自下而上和自上而下的方式重新设计斐波那契示例。

自下而上：

def fib(n):
  if n == 0:
    return 0
  if n == 1:
    return 1
  # table for tabulation
  table = [None] * (n+1) 
  table[0] = 0        # base case 1, fib(0) = 0
  table[1] = 1        # base case 2, fib(1) = 1
  # filling up tabulation table starting from 2 and going upto n
  for i in range(2,n+1):  
    # we have result of i-1 and i-2 available because these had been evaluated already
    table[i] = table[i-1] + table[i-2]  
  # return the value of n in tabulation table
  return table[n]    

print(fib(100))

-->
354224848179261915075

解决方案细分：

首先，我们创建了一个用于制表的列表，称为 。我们将它的大小设置为相等，因为我们将评估斐波那契总数 （）。接下来，我们通过将第 0 个和第 1 个索引分别设置为 and 来更新表中基本案例的值。剩下唯一要做的就是迭代桌子以填满它。在迭代结束时，我们将在 .tablen+1n+10,1,2...n01n^thtable

自上而下：

memo = {} #dictionay for Memoization

def fib(n):
  if n == 0: # base case 1
    return 0
  if n == 1: # base case 2
    return 1
  elif n in memo: # Check if result for n has already been evaluated
    return memo[n] # return the result if it is available
  else: # otherwise recursive step
    memo[n] = fib(n-1) + fib(n-2) # store the result of n in memoization dictionary
    return memo[n] # return the value

print (fib(100))

-->
354224848179261915075

解决方案细分（记忆）：

我们将对原始斐波那契算法进行的唯一更改是添加和使用这个新字典。我们已经全局定义了一个字典，因此它可用于所有调用（第 1 行）。接下来，在基本案例之后，我们检查是否已评估此数字。如果是，则返回其记忆值（第 8-9 行）。否则，我们需要评估这个结果，这就是我们进行递归调用的地方（第 11-12 行）。在返回之前，我们将结果记住在 中。我们不需要记住基本情况，因为它们通常已经是 O（1） 操作。fib()memo[n]