尝试在不使用其他算法的情况下使用递归求解

我正在努力更好地理解递归，以便更好地实现动态编程原理。我知道这个问题可以用Kadane的算法来解决；但是，我想使用递归来解决它。

问题说明：

给定一个整数数组，找到具有最大和的非相邻元素的子集。计算该子集的和。

我已经写了以下部分解决方案：

const maxSubsetSum = (arr) => {
let max = -Infinity
const helper = (arr, len) => {
if (len < 0) return max
let pointer = len
let sum = 0
while (pointer >= 0) {
sum += arr[pointer]
pointer -= 2
}
return max = Math.max(sum, helper(arr, len - 1))
}
return helper(arr, arr.length - 1)
}

如果我有这个数据：

console.log(maxSubsetSum([3, 5, -7, 8, 10])) //15 
//Our subsets are [3,-7,10], [3,8], [3,10], [5,8], [5,10] and [-7,10].

我的算法计算出13。我知道这是因为当我开始我的算法时，我的(n-2)值是计算出来的，但我没有考虑其他(n-3)或更多的子集，这些子集仍然验证了问题陈述的条件。我无法理解其他价值观的逻辑，请指导我如何实现这一点。

代码将递归(在helper内对helper的调用)与迭代(helper内的while循环)相结合。您应该只使用递归。

对于阵列的每个元素，都有两种选择：

跳过当前元素。在这种情况下，总和不会改变，可以使用下一个元素。所以递归调用是sum1 = helper(arr, len - 1, sum)
使用当前元素。在这种情况下，当前元素被添加到和中，并且必须跳过下一个元素。所以递归调用是sum2 = helper(arr, len - 2, sum + arr[len])

所以代码看起来像这样：

const maxSubsetSum = (arr) => {
const helper = (arr, len, sum) => {
if (len < 0) return sum
let sum1 = helper(arr, len - 1, sum)
let sum2 = helper(arr, len - 2, sum + arr[len])
return Math.max(sum1, sum2)
}
return helper(arr, arr.length - 1, 0)
}

您的想法是正确的，一旦从当前索引开始，就需要从(n-2)递归。但你似乎不明白，你不需要遍历你的数组来求和，然后递归。所以正确的方法是

包括当前项目并在剩余的n-2个项目或上递归
不包括当前项目，并在剩余的n-1个项目上重复

让我们看看这两个选择：

选择1:

您选择将该项目包括在当前索引中。然后在剩下的n-2项上递归。所以你的最大值可以是项目本身，而不添加到剩余的n-2项目中的任何一个，或者添加到n-2项目的一些项目中。因此Math.max(arr[idx]，arr[idx]+recurse(idx-2))是此选项的最大值。如果recurse(idx-2)给你-无穷大，你只需要考虑当前索引中的项目。

选择2:

您没有选择将该项目包括在当前索引中。所以只在剩下的n-1个项目上递归-recurse(n-1)

最后的最大值是这两个选项中的最大值。

代码为：

const maxSubsetSum = (arr) => {
let min = -Infinity
const helper = (arr, idx) => {
if ( idx < 0 ) return min
let inc = helper(arr, idx-2)
let notInc = helper(arr, idx-1)
inc = inc == min ? arr[idx] : Math.max(arr[idx], arr[idx] + inc)
return Math.max( inc, notInc )
}
return helper(arr, arr.length - 1)
}
console.log(maxSubsetSum([-3, -5, -7, -8, 10]))
console.log(maxSubsetSum([-3, -5, -7, -8, -10]))
console.log(maxSubsetSum([-3, 5, 7, -8, 10]))
console.log(maxSubsetSum([3, 5, 7, 8, 10]))

输出：

对于所有项目均为负数的情况：

在这种情况下，您可以说没有项目可以组合在一起以获得最大和。如果这是要求，那么结果应该为零。在这种情况下，只需将0作为默认结果即可返回0。这种情况下的代码是：

const maxSubsetSum = (arr) => {
const helper = (arr, idx) => {
if ( idx < 0 ) return 0
let inc = arr[idx] + helper(arr, idx-2)
let notInc = helper(arr, idx-1)
return Math.max( inc, notInc )
}
return helper(arr, arr.length - 1)
}

带记忆功能：

您可以为递归期间访问的索引存储此解决方案。只有一种状态，即索引，所以你的备忘录是一维的。带备注的代码为：

const maxSubsetSum = (arr) => {
let min = -Infinity
let memo = new Array(arr.length).fill(min)
const helper = (arr, idx) => {
if ( idx < 0 ) return min
if ( memo[idx] !== min) return memo[idx]
let inc = helper(arr, idx-2)
let notInc = helper(arr, idx-1)
inc = inc == min ? arr[idx] : Math.max(arr[idx], arr[idx] + inc)
memo[idx] = Math.max( inc, notInc )
return memo[idx]
}
return helper(arr, arr.length - 1)
}

基本版本足够简单，有明显的递归。我们要么将当前价值包含在我们的总和中，要么不包含。如果我们这样做，我们需要跳过下一个值，然后在剩余值上重复。如果我们不这样做，那么我们需要在当前值之后的所有值上重复。我们选择这两个结果中较大的一个。这几乎直接转化为代码：

const maxSubsetSum = ([n, ...ns]) =>
n == undefined  // empty array
? 0
: Math .max (n + maxSubsetSum (ns .slice (1)), maxSubsetSum (ns))

更新

这缺少了一个案例，在这个案例中，我们的最高总和只是数字本身。在这里(以及下面的片段中)

const maxSubsetSum = ([n, ...ns]) => 
n == undefined  // empty array
? 0
: Math .max (n, n + maxSubsetSum (ns .slice (1)), maxSubsetSum (ns))
console.log (maxSubsetSum ([3, 5, -7, 8, 10])) //15

但是，正如您在评论中所指出的，出于性能原因，我们可能真的想记住这一点。我们可以选择几种方法来做到这一点。一种选择是将我们在一次函数调用中测试的数组转换为可以用作Object或Map中的键的数组。它可能看起来像这样：

const maxSubsetSum = (ns) => {
const memo = {}
const mss = ([n, ...ns]) => {
const key = `${n},${ns.join(',')}`
return n == undefined
?  0
: key in memo
? memo [key]
: memo [key] = Math .max (n, n + maxSubsetSum (ns .slice (1)), maxSubsetSum (ns))
}
return mss(ns)
}
console.log (maxSubsetSum ([3, 5, -7, 8, 10])) //15

我们还可以使用一个助手函数来实现这一点，该函数对索引进行操作，并使用索引作为键进行记忆。它的复杂性也差不多。

然而，这有点丑陋，也许我们可以做得更好。

这种记忆有一个问题：它只持续当前运行。如果我要存储一个函数，我宁愿它为对相同数据的任何调用保留缓存。这意味着函数的定义中的记忆。我通常使用一个可重复使用的外部memoize助手来完成这项工作，类似于以下内容：

const memoize = (keyGen) => (fn) => {
const cache = {}
return (...args) => {
const key = keyGen (...args)
return cache[key] || (cache[key] = fn (...args))
}
}
const maxSubsetSum = memoize (ns => ns .join (',')) (([n, ...ns]) => 
n == undefined
? 0
: Math .max (n, n + maxSubsetSum (ns .slice (1)), maxSubsetSum (ns)))
console.log (maxSubsetSum ([3, 5, -7, 8, 10])) //15

memoize接受一个使用参数生成String键的函数，并返回一个接受您的函数并返回其记忆版本的函数。它通过在您的输入中调用键生成来运行，检查该键是否在缓存中。如果是，我们只需返回。如果不是，我们调用您的函数，将结果存储在该密钥下并返回。

对于这个版本，生成的键只是通过将数组值与','连接而创建的字符串。可能还有其他同样好的选择。

请注意，我们不能进行

const recursiveFunction = (...args) => /* some recursive body */
const memomizedFunction = memoize (someKeyGen) (recursiveFunction)

因为CCD_ 12中的递归调用将是到未存储的CCD_。相反，我们总是这样使用它：

const memomizedFunction = memoize (someKeyGen) ((...args) => /* some recursive body */)

但这只是一个很小的代价，因为它可以简单地用密钥生成器来封装函数定义，从而对函数进行记忆。

此代码已被接受：

function maxSubsetSum(A) {
return A.reduce((_, x, i) =>
A[i] = Math.max(A[i], A[i-1] | 0, A[i] + (A[i-2] | 0)));
}

但试图递归那么远(我试图提交Scott Sauyet的最后一个记忆示例)，我相信会导致运行时错误，因为我们可能会超过递归限制。

有趣的是，这里是自下而上的，自上而下的：)

function f(A, i=0){
if (i > A.length - 3)
return A[i] = Math.max(A[i] | 0, A[i+1] | 0);

// Fill the table
f(A, i + 1);
return A[i] = Math.max(A[i], A[i] + A[i+2], A[i+1]);
}
var As = [
[3, 7, 4, 6, 5], // 13
[2, 1, 5, 8, 4], // 11
[3, 5, -7, 8, 10] // 15
];
for (let A of As){
console.log('' + A);
console.log(f(A));
}

相关内容

最新更新

热门标签：