交互式动态编程教程:使用Python编写高效的程序

作者 : IT 大叔 本文共6653个字,预计阅读时间需要17分钟 发布时间: 2020-08-13

如果您正在学习Python,那么可能很难从编写示例代码到高效代码。随着技术的进步,程序运行时效率变得越来越重要,它是成功编写访谈和以后的实际解决方案的关键指标。

提高递归程序效率的一种方法是开始使用动态编程(一种节省时间的基于存储的技术)来代替暴力递归。动态编程使用最优原理,即如果对流程的所有步骤都进行优化,那么结果也将得到优化。在我们的例子中,最佳步骤是花费最少时间的步骤,这在编程中意味着它需要最少的新计算。

为了帮助您进入高效的Python代码,这里有一个快速教程,介绍什么是动态编程,为什么效率更高以及如何使用它来解决常见的面试问题。

这是我们今天要讲的

  • 什么是动态编程?
  • 为什么动态编程有效? 自下而上的动态编程
  • 自顶向下的动态编程
  • 动态编程实例
  • 练习动态编程问题
  • 接下来要学什么

通过动态编程最大化您的Python技能

获得有关动态编程各个部分的深入说明和动手实践。

Python中的动态编程:优化程序以提高效率

什么是动态编程?

动态编程是一种解决问题的技术,它通过将复杂问题递归分解为子问题来解决,然后分别解决这些子问题。动态编程可优化递归编程,并为我们节省以后重新计算输入的时间。

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

这使我们获得了动态编程的主要优势。动态编程无需重新计算这些共享的步骤,而是使我们能够在第一时间简单地存储每个步骤的结果,并在以后的每个时间重复使用。

注意:动态编程是较大类型的递归编程的特例,但是并非所有递归情况都可以使用动态编程

为什么动态编程有效?递归与DP

如果两者如此紧密地交织在一起,为什么在可能的情况下偏爱动态编程?这是因为暴力递归程序经常在面对重叠步骤时重复工作,从而在此过程中浪费了不必要的时间和资源。

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

注意:动态编程本质上是将空间效率与时间效率之间进行权衡,因为解决方案存储需要使用蛮力递归解决方案中不使用的空间。

动态编程实例

现实世界中的动态编程

与计算机不同,动态编程等基于内存的过程对人类而言是直观的。考虑以下真实示例:

想象一下,您想去几条街外的新杂货店,但是您不知道如何到达那里。要解决通往商店的路线的子问题,您可以在智能手机的地图上查找路线,然后前往目的地。

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

取而代之的是,我们自然而然地动态思考,记住了从初次查找它们到商店的方向,因此,当我们将来去时,不需要花时间查找它们。

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

阶乘问题

我们可以在现实生活中看到动态编程比递归更有效的方法,但是让我们看看它在Python代码中的作用!

下面,我们有两个解决方案,它们都找到给定输入的斐波那契数,然后显示程序运行时的图表。左选项卡是简单的蛮力递归,而右选项卡则使用动态编程。

看区别。

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
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

如您所见,在动态解决方案的代码中,我们增加了存储旧结果的能力(第12行),然后再进行下一个递归步骤(第13-15行)。我们将在本文后面看到更复杂的动态解决方案及其分步细分。

请注意,在比较每个图形时,近线性时间复杂度如何, 上)与递归函数的二次时间复杂度相比,动态解决方案的,即使在以后的情况下,其性能也要好得多。 O(2 ^ n)

自下而上的动态编程

并非所有动态解决方案都以相同的方式工作。有些是自底向上构建的,而另一些是自顶向下构建的。可以从每个问题如何开始以及子问题结果的存储方式中找到区别。

自下而上的动态编程解决方案首先查看最小的子问题(称为基本案例),然后逐步解决每个子问题。随着每个子问题的解决,其解决方案将被保存并用于解决下一个最低的子问题。最后,这些建筑解决方案将为主要问题提供答案。

什么是制表法?

制表是从下至上的方法顺序存储子问题的结果的过程。

在表格中,我们无需选择需要解决的子问题,而是选择解决基本案例和主要问题之间的每个子问题。这种顺序顺序使制表可以使用列表或数组,因为这些集合以特定顺序组织信息。

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

自顶向下的动态编程

自上而下的动态编程与自下而上的相反。自上而下的解决方案首先着眼于主要问题,并将其分解为越来越小的必要问题,直到达到基本情况为止。这是构建递归解决方案的最常用方法。

在使用这种形式的递归链时,自上而下的动态编程只能按需解决子问题,而不能按顺序解决所有问题。

什么是记忆化?

备忘是一种以自上而下的方式存储子问题结果的过程。

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

在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))

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

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))

首先,我们出于列表目的创建了一个名为的列表tablen+1由于我们要评估n+1斐波纳契总数(0,1,2...n),因此将其大小设置为。下一步,我们通过设置0更新的表中的基例的值 1个第一索引01分别。剩下要做的唯一事情就是遍历表以将其填满。在迭代结束时,我们将 在的最后一个索引处具有第n 斐波那契数table

继续学习。

获得更多的交互式Python示例,并练习类似的问题,所有这些问题均由当前的软件开发人员编写和解释。

Python中的动态编程:优化程序以提高效率

练习动态编程问题

现在尝试一下!这是从我们的交互式Python动态编程课程中获得的一些实践问题。这些问题中的许多问题在编写面试代码以测试您的动态编程技能时很常见。熟悉这些问题将使您成为更好的候选人。

尝试弄清楚用自下而上或自上而下解决每个问题是否最佳。如果卡住,请随时检查提示或解决方案。

背包问题

问题陈述:

给定一个权重列表和一个成本列表,找到形成最高累积价格,受背包容量限制的事物的最佳子集。

您不应更改给定功能的签名;但是,您可以创建一个具有不同签名的新函数,然后从提供的函数中调用它。

尝试想出一个解决此问题的简单方法。一旦实现了该功能,就可以添加备忘录以解决更复杂的问题。

输入样例:

权重= [1, 2, 4, 6]

价格= [4, 2, 4, 7]

容量= 7

def solveKnapsack(weights, prices, capacity, index, memo):
  # base case of when we have run out of capacity or objects
  if capacity <= 0 or index >= len(weights): 
    return 0
  # check for solution in memo table
  if (capacity, index) in memo: 
    return memo[(capacity, index)]
  # if weight at index-th position is greater than capacity, skip this object
  if weights[index] > capacity: 
    # store result in memo table
    memo[(capacity, index)] = solveKnapsack(weights, prices, capacity, index + 1, memo) 
    return memo[(capacity, index)] 
  # recursive call, either we can include the index-th object or we cannot, we check both possibilities and return the most optimal one using max
  memo[(capacity, index)] = max(prices[index]+solveKnapsack(weights, prices, capacity - weights[index], index+1, memo),
        solveKnapsack(weights, prices, capacity, index + 1, memo)) 
  return memo[(capacity, index)]

def knapsack(weights, prices, capacity):
  # create a memo dictionary
  memo = {} 
  return solveKnapsack(weights, prices, capacity, 0, memo)

print(knapsack([2,1,1,3], [2,8,1,10], 4))

解决方案分类:

在此问题中,很难看到重叠的问题,因为它们没有遵循特定的模式。但是如果仔细观察,您会发现容量和索引元组经常重复。所有这些子问题都有相同的答案。查看以下可视化。

交互式动态编程教程:使用Python编写高效的程序插图

从可视化中可以看到,我们可以基于容量和索引的元组进行记忆。这是该代码中上一个具有简单递归的唯一附加组件。在递归步骤之前,我们在备注表中检查结果是否已经可用。同样,在评估结果之后,我们再次将其存储在备忘录表中。

找零问题

这是编码采访中经常问到的“零钱问题”的一个版本。

问题陈述:

给定货币清单,您需要计算代表一定金额的方式数量。例如,如果您只有两种钞票,10美元和20美元,而您想代表30美元,则只有两种方式:

  • 3张10美元的钞票
  • 1张20美元的钞票和1张10美元的钞票。

设计算法时,请特别注意不要过度计数。$ 30可以用$ 20 + $ 10以及$ 10 + $ 20表示,但这是同一回事。因此,您不应该同时考虑这两种情况。

一个简单的递归解决方案对于大输入将超时。因此,您应该尝试编写动态编程算法。从递归解决方案开始,然后发展为动态解决方案。

def countways_(bills, amount, index):
  if amount == 0:     # base case 1
    return 1
  if amount < 0 or index >= len(bills):      # base case 2
    return 0
  # count the number of ways to make amount by including bills[index] and excluding bills[index]
  return countways_(bills, amount - bills[index], index) + countways_(bills, amount, index+1)

def countways(bills, amount):
  return countways_(bills, amount, 0)

print(countways([1,2,5], 5))

递归解决方案细分:

在一组事物中找到不同的组合并不困难。实际上,我们在本课程中遇到的第一个问题是找到字符串的不同排列。具有挑战性的一点是如何避免由于相同排列而导致的计数过度。

例如,$ 10 + $ 20加了$ 30,所以$ 20 + $ 10也加了。在排列的情况下,这两个序列将是不同的,但是在组合的情况下,它们是相同的,这意味着我们不能对它们进行两次计数。我们通过限制每个递归调用使用账单的子集来实现这一点。

此解决方案的关键部分是第7行中两个递归调用的总和。要计算总金额,某些组合将包含bills[index]或不会提供的特定帐单。因此,我们可以简单地算出这两种可能性。第一个调用countways_算作bills[index]解决方案的一部分,而第二个调用则跳过它。让我们看一下该算法的简单可视化。

def countways(bills, amount):
  if amount <= 0:
    return 0
  dp = [[1 for _ in range(len(bills))] for _ in range(amount + 1)]
  for amt in range(1, amount+1):
    for j in range(len(bills)):
      bill = bills[j]
      if amt - bill >= 0:
        x = dp[amt - bill][j]
      else:
        x = 0
      if j >= 1:
        y = dp[amt][j-1]
      else:
        y = 0
      dp[amt][j] = x + y
  return dp[amount][len(bills) - 1]

print(countways([1,2,5], 5))

接下来要学什么

完成我们的教程后,您可以希望看到该工具对Python开发人员的强大功能。这些概念不仅在编码访谈中经过测试,而且对于创建高效的现实世界Python应用程序也必不可少。

现在您已经迈出了第一步,最好的事情就是研究何时使用自上而下与自下而上的方法,并继续练习各种类型的问题。

到最后,您将知道如何识别动态编程问题,了解何时使用自上而下或自下而上的知识,并有足够的深度练习使任何面试官都赞叹不已。

恭喜您进一步完善了Python功能。今天,我们带您了解了动态编程的内容,原因和方式,并获得了一些真正的面试问题练习。

从编写基本代码到高效代码,这标志着您学习的一个伟大里程碑。虽然这可能是一条艰难的学习曲线,但要知道,您创建的每个动态解决方案都会使您在我们的现代开发空间中更加有资格和有需求!

免责声明:
1. 本站资源转自互联网,源码资源分享仅供交流学习,下载后切勿用于商业用途,否则开发者追究责任与本站无关!
2. 本站使用「署名 4.0 国际」创作协议,可自由转载、引用,但需署名原版权作者且注明文章出处
3. 未登录无法下载,登录使用金币下载所有资源。
IT小站 » 交互式动态编程教程:使用Python编写高效的程序

常见问题FAQ

没有金币/金币不足 怎么办?
本站已开通每日签到送金币,每日签到赠送五枚金币,金币可累积。
所有资源普通会员都能下载吗?
本站所有资源普通会员都可以下载,需要消耗金币下载的白金会员资源,通过每日签到,即可获取免费金币,金币可累积使用。

发表评论