区间动态规划

Question

区间动态规划

algorithmdynamic

4

我正在研究一道算法问题，但在加速它方面遇到了难题。

我有一个函数 f(i,j)，其中 i 和 j 是整数，满足某个上限 n 的条件 1 <= i <= j <= n。这个函数已经被写好。

此外，这个函数满足等式 f(i, j) + f(j, k) = f(i, k)。

我需要计算许多不同的 x,y 对应的 f(x,y)。假设 n 足够大，存储每个可能的 x,y 对应的 f(x,y) 会占用太多空间。

是否有已知的算法解决这种类型的问题？我目前使用的方法是对 f 进行记忆化，并尝试通过使用上述相等性将 x,y 减少为先前计算过的数字对，但我猜想我没有以聪明的方式减少，这浪费了我的时间。

编辑：假设以朴素方式计算 f(i, j) 的时间与 j-i 成比例。

- Titandrake

我可以在O(log n)时间和O(n)空间内完成。 - John Dvorak

“O(1)”时间和“O(n^2)”空间是微不足道的，正如你所说。 - John Dvorak

2

根据上述身份，f(i,i)=0。 - John Dvorak

实际上 f(i,i) = 0, f(i,j) = - f(j, i)。 - UmNyobe

@Titandrake，您能更具体地说明您的函数吗？或者我可以假设它类似于F(i,j)=L(j)-L(i)吗？ - MissingNumber

显示剩余4条评论

3个回答

2

该函数符合规则。

f(i, j) + f(j, k) = f(i, k)

正如你所说。

因此，将函数修改为类似于 f(i,j) =g(j)-g(i) 的形式，其中 g(i)= f(1,x)。

所以，

f(i,k)=g(k)-g(i)
      =g(k)-g(j)+g(j)-g(i)
      =f(j,k) + f(i,j)

我认为，如果您尝试存储f(i,j)的所有组合，则空间成本约为O(n^2)，因此最好存储所有i值的g(i)值，这需要O(n)的空间。

因此，每当您需要查找f(i,j)时，您实际上可以将其查找为g(j)-g(i)。

如下：

  f(i,j)= g(j)-g(i) // as we already calculated and stored the g(i) .

- MissingNumber

我认为OP不希望我们对底层函数f做任何假设。 - Rerito

2

如果我们定义 g(x) = f(1, x)，那么这个解决方案就可行。然后 f(i, j) = g(j) - g(i)，并且该解决方案需要 O(n) 空间，O(n) 准备时间和 O(1) 时间。 - Titandrake

f(j) 未定义。根据定义，f 是定义在 IxI 上的函数而不是 I 上的函数。我认为您可能需要使用另一个函数（如果可能的话）。 - UmNyobe

0

这是一个需要O(n)空间，O(n^2)设置时间和每次评估的O(1)时间的解决方案。

我们有f(i, j) = -f(j, i)对于i <= j。

给定f(i, k) = f(i, j) + f(j, k)。因此，f(i, k) = f(i, j) + f(j, k) = -f(j, i) + f(j, k)。在设置阶段，任意固定j = 1。然后，计算每个i的f(1, i)并存储结果。这需要O(n)空间和O(n^2)时间：运行时间为1、2、3、...、n的n个评估。

对于查询f(i, k)，我们需要两个常数时间查找f(i, 1)和f(k, 1)。

- blubb

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- John Dvorak · Accepted Answer

您可以使用大小为2的幂次方间隔的隐式树：

为每个i存储f(i,i+1)
为每个偶数i存储f(i,i+2)
对于每个可被四整除的i，存储f(i,i+4)
...

将会有O(log n)个表格（确切地说是floor(log_2(n))），总大小为O(n)（约为2*n）。

要检索f(i,j)，其中i<=j：

找到i、j不同的最高位。
让n是具有此位设置并清除所有较低位的值。这保证了以下步骤将始终成功：
通过反复从右侧截取尽可能大的块来找到f(i, n)
通过反复从左侧截取尽可能大的块来找到f(n, j)

检索最多访问每个表两次，因此运行时间为O(log n)。