JavaScript数组记忆化搜索技巧

一分耕耘，一分收获！既然都打开这篇《JavaScript数组记忆化搜索实现方法》，就坚持看下去，学下去吧！本文主要会给大家讲到等等知识点，如果大家对本文有好的建议或者看到有不足之处，非常欢迎大家积极提出！在后续文章我会继续更新文章相关的内容，希望对大家都有所帮助！

数组记忆化搜索通过存储已计算结果避免重复计算，提升效率；设计记忆化数组时需确保其结构能唯一标识问题状态，通常使用多维数组对应索引，如斐波那契数列用一维数组 memo[n] 存储，最长递增子序列用 memo[index] 记录以某索引开始的最长长度；记忆化搜索是自顶向下的递归方法，与自底向上的动态规划不同，更适用于状态空间不规则的问题；边界条件和无效状态应在递归开头检查并返回确定值，防止无限递归；空间复杂度方面，若记忆化数组仅单次调用使用，可在函数结束后释放，或通过优化仅保留必要状态，如斐波那契数列可改为迭代方式仅用常数空间，从而降低内存占用。

数组记忆化搜索，简单来说，就是利用数组来存储已经计算过的结果，避免重复计算，提升效率。

javascript实现数组记忆化搜索的关键在于：构建一个与问题规模相对应的数组，用于存储中间结果；在搜索过程中，先检查数组中是否已经存在结果，存在则直接返回，否则进行计算并将结果存入数组。

如何设计记忆化数组的结构？

记忆化数组的结构必须能够唯一标识问题的状态。对于数组相关的记忆化搜索，通常可以使用多维数组，每一维度对应数组的一个索引。例如，如果需要记忆化数组中从索引 i 到索引 j 的子数组的某种计算结果，可以使用一个二维数组 memo[i][j] 来存储。 数组的具体维度和大小取决于问题的具体定义和约束条件。 考虑一个简单的例子，计算斐波那契数列的第 n 项。 我们可以用一个一维数组 memo[n] 来存储已经计算过的斐波那契数。

function fibonacciMemo(n, memo = []) {
  if (memo[n] !== undefined) {
    return memo[n];
  }
  if (n <= 1) {
    return n;
  }
  memo[n] = fibonacciMemo(n - 1, memo) + fibonacciMemo(n - 2, memo);
  return memo[n];
}

console.log(fibonacciMemo(10)); // 输出 55

这段代码中，memo 数组存储了已经计算过的斐波那契数，避免了重复计算。如果 memo[n] 已经存在，则直接返回，否则计算 fibonacciMemo(n - 1) 和 fibonacciMemo(n - 2)，并将结果存入 memo[n]。

记忆化搜索与动态规划的区别？

记忆化搜索和动态规划都用于解决具有重叠子问题的问题，但它们采用不同的方法。记忆化搜索是自顶向下的，从问题的顶层开始，递归地解决子问题，并将结果存储起来。动态规划是自底向上的，先解决最小的子问题，然后逐步解决更大的子问题，直到解决整个问题。

虽然两种方法都可以提高效率，但在某些情况下，记忆化搜索可能更直观，更容易实现。特别是当问题的状态空间不是完全规则时，动态规划可能需要更复杂的迭代逻辑，而记忆化搜索可以更自然地处理这些情况。

例如，考虑一个寻找数组中最长递增子序列的问题。使用动态规划，你需要仔细考虑状态转移方程，并以正确的顺序迭代计算每个状态。而使用记忆化搜索，你可以直接从整个数组开始，递归地寻找以每个元素结尾的最长递增子序列，并将结果存储起来。

如何处理边界条件和无效状态？

在记忆化搜索中，处理边界条件和无效状态至关重要。边界条件通常是递归的终止条件，例如，当数组为空或只包含一个元素时。无效状态是指不符合问题约束条件的状态，例如，当索引超出数组范围时。

处理边界条件和无效状态的方法通常是在递归函数的开头进行检查。如果遇到边界条件或无效状态，则直接返回一个预定义的值，例如 0 或 null。这可以防止无限递归和错误的结果。

function longestIncreasingSubsequenceMemo(arr, index, memo = {}) {
  if (index === arr.length) {
    return 0; // 边界条件：到达数组末尾
  }

  if (memo[index] !== undefined) {
    return memo[index]; // 检查是否已经计算过
  }

  let maxLength = 1; // 至少包含自身

  for (let i = index + 1; i < arr.length; i++) {
    if (arr[i] > arr[index]) {
      maxLength = Math.max(maxLength, 1 + longestIncreasingSubsequenceMemo(arr, i, memo));
    }
  }

  memo[index] = maxLength;
  return maxLength;
}

function findLongestIncreasingSubsequence(arr) {
  let maxLength = 0;
  for (let i = 0; i < arr.length; i++) {
    maxLength = Math.max(maxLength, longestIncreasingSubsequenceMemo(arr, i, {}));
  }
  return maxLength;
}

console.log(findLongestIncreasingSubsequence([1, 3, 2, 4, 5])); // 输出 4

在这个例子中，longestIncreasingSubsequenceMemo 函数使用 memo 对象来存储已经计算过的最长递增子序列的长度。如果 index 等于数组的长度，则返回 0。在递归调用之前，先检查 memo[index] 是否存在，如果存在则直接返回。

空间复杂度优化：何时可以释放记忆化数组？

记忆化搜索虽然提高了时间效率，但同时也增加了空间复杂度。在某些情况下，记忆化数组可能占用大量的内存。因此，在不再需要记忆化数组时，应该及时释放它，以避免内存泄漏。

确定何时可以释放记忆化数组取决于问题的具体情况。一般来说，如果记忆化数组只在单个函数调用中使用，则可以在函数返回后立即释放它。如果记忆化数组需要在多个函数调用之间共享，则需要在所有函数调用完成后再释放它。

在 JavaScript 中，可以通过将记忆化数组设置为 null 或 undefined 来释放它。这将使垃圾回收器能够回收数组占用的内存。

然而，更进一步的优化可能涉及到只保留必要的中间结果。例如，在斐波那契数列的例子中，你只需要保存最近的两个斐波那契数，而不是整个数组。

function fibonacciOptimized(n) {
  if (n <= 1) {
    return n;
  }

  let a = 0;
  let b = 1;
  let result = 0;

  for (let i = 2; i <= n; i++) {
    result = a + b;
    a = b;
    b = result;
  }

  return result;
}

console.log(fibonacciOptimized(10)); // 输出 55

这个优化后的版本只使用三个变量来存储中间结果，大大降低了空间复杂度。

今天关于《JavaScript数组记忆化搜索技巧》的内容介绍就到此结束，如果有什么疑问或者建议，可以在golang学习网公众号下多多回复交流；文中若有不正之处，也希望回复留言以告知！