动态编程基础——第 1 部分

有两种方法可以使用动态规划来解决问题。在这篇文章中，我们将看到记忆化方法。

1. 记忆
2. 制表

什么是动态规划？

它是一种简单递归的优化技术。它大大减少了解决给定输入问题的时间。它将问题分解为嵌套的子问题并计算这些子问题的结果。这些子问题的结果被重用以避免重新计算。它将问题的时间复杂度从指数降低到多项式。这种重用子问题的结果可以通过两种方式完成——记忆和制表。

什么是记忆？

要通过记忆方法解决问题，首先使用递归解决给定的问题。然后通过将结果保存在字典或适合要求的数据结构中来应用记忆。

让我们用 Scala 中的一个简单示例（不是常规的斐波那契序列生成）来演示该方法。 Scala 中没有足够的资源用于动态编程，所以我希望这会有所帮助。

如何通过制表法解决相同的问题将在动态规划基础 – 第 2 部分帖子中进行说明。请随时检查。

没有记忆：

问题陈述：以下函数有两个参数——targetSum 和一个整数元素数组，如果数组元素的任何组合可以求和到 targetSum，则返回 true。 该组合可以是数组中的任意数量，考虑任意次数。

例如， targetSum:3 , arr:Array(1,4,7) => 返回 true，因为 1+1+1=3

没有记忆代码解释：

每次通过递归地从数组中减去元素来更新 targetSum 并查看是否至少有任何一个组合导致 0（这意味着该组合可以总计为 targetSum）。 如果是，则函数的返回值为真。

对较大的 targetSum 使用不带记忆的常规递归的问题是运行时变慢，有时甚至出现内存不足的执行错误。

def recursion(targetSum: Int, arr: Array[Int]):Boolean={
if(targetSum == 0) true
else if(targetSum < 0) false
else{
arr.map(i=>{
var temp=targetSum-i
recursion(temp,arr)
}).exists(j=>j==true)
}

recursion(7,Array(5,3,4,7))
recursion(300,Array(7,14)) // slows down the runtime

带记忆：

带记忆代码说明：

核心逻辑保持不变。 不同之处在于每次计算值时，它都存储在字典中，如果值已经在字典中，它会被重用。 这样，可以避免大量的重新计算。

import scala.collection.mutable.Map
def recursion_memoized(targetSum: Int, arr: Array[Int],memo:Map[Int, Boolean]):Boolean={
if(targetSum == 0) true
else if(targetSum < 0) false
else if(memo.contains(targetSum)) memo(targetSum)
else{
 arr.map(i=>{
 var temp=targetSum-i
 memo(targetSum)=recursion_memoized(temp,arr,memo)
 memo(targetSum)
}).exists(j=>j==true)
}
}recursion_memoized(7,Array(5,3,4,7),Map())

结论：

通过使用记忆，我们通过重用字典中的值而不是重新计算值来减少运行时间。