译者|陆新旺评论|梁策孙淑娟动态规划已经有十多年了。根据维基百科，它既是一种数学优化方法，也是一种计算机编程方法。对于真正应用动态规划的问题，它必须具有两个关键属性：最优结构和重叠子结构。本文不会深入探讨动态规划的细节，而是重点介绍重叠子结构如何成为动态规划的关键属性之一。讨论这一点很重要，因为它涉及到随后的存储解决方案问题。本文解释了什么是备忘录，它对Javascript开发人员有什么价值，以及如何使用它来改进Javascript功能，让您深入了解备忘录本身以及它对优化您的应用程序意味着什么。在本文中，我们将讨论以下主题：什么是备忘录备忘录的主要概念功能有和没有备忘录的比较什么是备忘录？值存储方法。备忘录就是记录一个解决问题的结果，这样下次需要再次做同样的事情时，就不用重新计算了。但是函数使用memoization需要满足一定的条件：必须是引用透明的，即调用函数的效果与用返回值替换函数调用的效果完全一样时才能使用的功能。大多数编程语言如Ruby、C++、Python中都有备忘录，甚至这些语言中还有许多库可以使它变得简单。在本文中，我们将重点关注Javascript。编程语言可能不同，但是概念和思想是一样的。备忘录概念备忘录需要理解以下两个概念：1.引用透明性2.查找表1.引用透明性如果一个表达式可以被其对应的值替换（反之亦然）而不改变程序的行为，那么它就是它称为参照透明性。这要求表达式必须是纯的，即它必须对相同的输入求出相同的值，并且必须在没有副作用的情况下求值。引用不透明的表达式称为引用不透明。有了上面的解释，我们可以很快的把它和备忘录的行为联系起来，这个概念让我们可以写一个带有备忘录的函数。2.查找表查找表（LUT）是一个数组，它用更简单的数组索引操作代替运行时计算。这个过程称为“直接寻址”，LUT与哈希表的不同之处在于它检索一个值。比较有和没有备忘录的函数以经典斐波那契数列的定义为例：1.functionFibo(n){2.if(n<2){3.returnn;4.}5.returnFibo(n-1)+斐波那契(n-2);6.}如您所料，一旦您开始使用大于20的数字，这个过程就会变得非常缓慢。当你处理35左右的数字时，计算机可能无法坚持下去。解决方法是记录调用函数的返回结果1.varIterMemoFib=function(){2.varcache=[1,1];3.varfib=function(n){4.if(n>=cache.length){5.for(vari=cache.length;i<=n;i++){6.cache[i]=cache[i-2]+cache[i-1];7.}8.}9.returncache[n];10.}11.12.returnfib;13.}();这部分有点繁琐，可读性不强，或者可以让电脑辅助：1.Fib=Fib.memoize();由于技术（浏览器安全策略）限制，memento函数的参数只能是数组或标量值，不能是对象。下面的代码扩展了Function对象以添加备忘录功能。如果函数是方法，则可以将对象传递给memoize()。1.Function.prototype.memoize=function(){2.varpad={};3.varself=this;4.varobj=arguments.length>0?arguments[i]:null;5.6.varmemoizedFn=function(){7.//Copytheargumentsobjectintoanarray:allowsittobeusedas8.//acachekey.9.varargs=[];10.for(vari=0;i
