区间动态规划

Question

我正在研究一个算法问题，在加速的过程中遇到了困难。

我有一个函数f(i,j)，其中i和j是整数，使得1 <= i <= j <= n为某个上限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成比例。

Answer 1

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

每个i

• Store的
• 商店f(i,i+1)每个偶数i
• Store的f(i,i+4)每个可被four
• ...

整除的i

将有O(log n)表(确切地说，是floor(log_2(n)))，总大小为O(n) (~2*n)。

检索f(i,j) where i<=j

• 查找i和j不同的最高位。
• 设置n为设置了此位的值，并清除所有低位。这保证了以下步骤将始终通过从右侧切出尽可能大的块来重复succeed:
• find f(i, n)通过从左侧切出尽可能大的块来重复

检索至多访问每个表两次，因此在O(log n)中运行。

Answer 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在o(n)空间中的所有值的g(i)值

所以当你需要求f(i，j)的时候，你可以用g(j)-g(i)来求它。

作为

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

Answer 3

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

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

给定的是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)的两个常量时间查找。