数组记忆化搜索通过存储已计算结果避免重复计算，提升效率；设计记忆化数组时需确保其结构能唯一标识问题状态，通常使用多维数组对应索引，如斐波那契数列用一维数组 memo[n] 存储，最长递增子序列用 memo[index] 记录以某索引开始的最长长度；记忆化搜索是自顶向下的递归方法，与自底向上的动态规划不同，更适用于状态空间不规则的问题；边界条件和无效状态应在递归开头检查并返回确定值，防止无限递归；空间复杂度方面，若记忆化数组仅单次调用使用，可在函数结束后释放，或通过优化仅保留必要状态，如斐波那契数列可改为迭代方式仅用常数空间，从而降低内存占用。
数组记忆化搜索，简单来说，就是利用数组来存储已经计算过的结果，避免重复计算，提升效率。
javascript实现数组记忆化搜索的关键在于：构建一个与问题规模相对应的数组，用于存储中间结果；在搜索过程中，先检查数组中是否已经存在结果，存在则直接返回，否则进行计算并将结果存入数组。
如何设计记忆化数组的结构？
记忆化数组的结构必须能够唯一标识问题的状态。对于数组相关的记忆化搜索，通常可以使用多维数组，每一维度对应数组的一个索引。例如，如果需要记忆化数组中从索引 i 到索引 j 的子数组的某种计算结果，可以使用一个二维数组 memo[i][j] 来存储。 数组的具体维度和大小取决于问题的具体定义和约束条件。 考虑一个简单的例子，计算斐波那契数列的第 n 项。 我们可以用一个一维数组 memo[n] 来存储已经计算过的斐波那契数。
立即学习“Java免费学习笔记（深入）”；
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这个优化后的版本只使用三个变量来存储中间结果，大大降低了空间复杂度。
