译者|赵庆尧审稿人|动态规划通常是技术面试、设计审查会议或与开发人员互动中的关键话题。本文将解释什么是动态规划以及为什么要使用它。为了清楚地解释动态规划的概念，我将使用Swift代码示例来说明，其他语言也适用。一种思维方式与特定的编码语法或设计模式不同，动态规划不是一种特定的算法，而是一种思维方式。因此，具体到实现层面，动态规划有很多表现形式。动态规划的核心思想是将一个大问题分解成多个部分。同时，推荐的动态规划方式也需要数据的存储和复用，以提高算法效率。软件开发中的许多问题都可以用各种形式的动态规划来解决。关键是知道何时使用简单变量以及何时使用复杂数据结构或算法来设计最佳解决方案。例如，代码变量可以被认为是动态规划的一种基本形式。变量的目的是在内存中保存一个特定的位置，以便稍后调用。//非记忆函数funcaddNumbers(lhs:Int,rhs:Int)->Int{returnlhs+rhs}//记忆函数funcaddNumbersMemo(lhs:Int,rhs:Int)->Int{letresult:Int=lhs+rhsreturnresult}addNumbersMemo上面做了简单的介绍，而动态规划解决方案旨在保留以前看到的值，一种称为记忆的设计技术。代码挑战-数字对多年来，我对数十名准备在Apple、Facebook和亚马逊等顶级公司面试的开发人员进行了模拟面试，大多数人都非常乐意跳过那些可怕的现场白板面试或带回家编程项目。但事实是，其中许多问题旨在测试一个人对计算机科学基础知识的基本理解。例如下面的情况：/*在一次技术面试中，给你一个数组，需要找到一对等于给定目标值的数字。数字可以是正数、负数或两者兼而有之。你能设计一个在O(n)线性时间内工作的算法吗？letsequence=[8,10,2,9,7,5]letresults=pairValues(sum:11)=//returns(9,2)*/对于开发者来说，解决问题通常有很多种方法。在这种情况下，我们的目标是找到数字对以达到预期的结果。人们可以用肉眼快速浏览数字序列，很容易找到一对9和2。但是，算法需要检查和比较序列中的每个值，或者开发更精简的解决方案来帮助我们找到了我们正在寻找的价值。接下来，我将分别介绍这两种技术。BruteForce第一种方法是查看第一个值，然后逐个检查每个值以确定差异是否达到目的。例如，我们的算法检查数组中的第一个值8，然后在其余值中找到3（例如11-8=3）。但是我们发现这一组中没有3，那么算法继续以同样的方式寻找下一个值（即例子中的10），直到找到匹配成功的一对。在不深入大O符号的细节的情况下，我们可以认为此类解决方案的平均时间复杂度为O(n^2)或更大，这主要是因为我们的算法的工作方式使得每个值都与其他值进行比较.该过程可以通过如下代码实现：letsequence=[8,10,2,9,7,5]//非记忆法-O(n^2)funcpairNumbers(sum:Int)->(Int,Int){forainsequence{letdiff=sum-aforbinsequence{if(b!=a)&&(b==diff){return(a,b)}}}return(0,0)}memoryApproach接下来，让我们使用记忆的思维方式来解决问题。在执行代码之前，我们需要考虑存储先前计算的值如何帮助简化流程。使用标准数组是可行的，但集合对象（也称为哈希表或哈希表）也可以提供优化的解决方案。//记忆方法-O(n+d)funcpairNumbersMemoized(sum:Int)->(Int,Int){varaddends=Set
