arrays - 寻找通过数组的最低价格的算法

Question

我一直在思考以下问题:

我们得到了一个包含 n 个数字的数组。我们从第一个索引开始，我们的任务是到达最后一个索引。每一步我们都可以向前跳一两步，我们跳到的索引处的数字代表我们访问该索引所需支付的成本。我们需要找到到达数组末尾的最便宜的方法。

例如，如果数组如下所示:[2,1,4,2,5] 到达末尾的最便宜方法是 10:我们访问索引 1->2->4->5 我们必须支付 2+1+2+5 = 10 这是最便宜的方式。设 f(i) 是达到索引 i 的最低价格。通过实现 f(i) = arr[i] + min(f(i-1),f(i- 2))

但这里有一个转折点:该数组会更新多次，每次更新后，我们都需要能够在 O(logn) 时间内判断出目前最便宜的方法。通过告知将更改的索引以及将更改为的数字来更新数组。例如，更新可能是 arr[2] = 7 将我们的示例数组更改为 [2,7,4,2,5]。现在最便宜的方式是 11。

现在我们如何在 O(logn) 时间内支持这些更新？有什么想法吗？

到目前为止，这是我想出的:首先，我会像前面描述的那样为动态规划创建一个数组 f。我将按以下方式将此数组的内容存储在线段树 s 中:s(i) = f(i) - f(i-1)。这将允许我在 O(logn) 时间内更新 f 的间隔(为每个值添加一个常数)，并在 中询问给定索引处的值O(logn) 时间。这会很方便，因为在一些更新之后，通常会发生 f 中的所有值都需要在 f 中的某个给定索引之后增加一个常数。因此，通过在每次更新后询问线段树中 s(n) 的值，我们将获得所需的答案。

然而，更新后可能会发生不同的事情:

1. f 中只有一个值需要更新。例如，如果 [2,1,4,2,5,4,9,3,7] 更改为 [2,1,9,2,5,4,9, 3,7] 只有 f(3) 需要更新，因为无论如何都没有最便宜的方法通过 3. 索引。
2. f 中给定索引之后的所有值都需要用常量更新。这就是线段树的用武之地。
3. f 中给定索引之后的每个其他值都需要用常量更新。
4. 更随机的东西。

Answer 1

好吧，我设法自己解决了这个问题，所以我决定与您分享解决方案。 :)

我在动态规划和线段树方面走在了正确的轨道上，但在我之前的尝试中我以错误的方式提供了线段树。

以下是我们如何在 O(logn) 时间内支持更新:这个想法是使用二叉树，其中树的叶子代表当前数组，每个节点存储 4 个不同的值。

1. v1 = 从最左边的后代到最右边的后代的最低成本
2. v2 = 从最左边的后代到第二个最右边的后代的最低成本
3. v3 = 从第二个最左边的后代到最右边的后代的最低成本
4. v4 = 从第二个最左边的后代到第二个最右边的后代的最低成本

对于后代，我指的是节点的后代也是叶子。

更新数组时，我们更新叶节点的值，然后更新其所有祖先节点，直至根节点。由于在每个节点上我们都已经知道其两个子节点的所有这 4 个值，因此我们可以轻松计算当前父节点的新 4 个值。举个例子:v1_current_node = min(v2_leftchild+v1_rightchild, v1_leftchild+v1_rightchild, v1_leftchild+v3_rightchild)。所有其他三个值都可以用类似的方式计算。

由于每片叶子只有 O(logn) 个祖先，并且所有 4 个值都是在 O(1) 时间内计算的，所以只需要 O( logn) 更新整棵树的时间。

现在我们知道了每个节点的 4 值，我们可以用类似的方式计算从第一个节点到第 n: 个节点的最低成本，方法是使用我们路径中 2 的最高幂的节点在树中加起来为 n。例如，如果 n = 11 我们想知道从第一个节点到第十一个节点的最低成本，这可以通过使用覆盖叶子 1-8 的节点的信息来完成>，覆盖叶子9-10和叶子节点11的节点。对于所有这三个节点，我们都知道所描述的 4 值，我们可以以类似的方式组合这些信息来找出答案。最多我们需要考虑 O(logn) 个节点来执行此操作，所以这不是问题。