间隔动态编程

Question

我正在研究一个算法问题,而且我正在加快速度.

我有一个函数f(i,j),其中i和j是整数,1 <= i <= j <= n对于某些上限n.这个功能已经写好了.

此外,该功能满足相等性f(i, j) + f(j, k) = f(i, k).

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

是否有针对此类问题的已知算法？我现在正在使用的那个记忆f并试图x,y通过使用上面提到的相等来减少到先前计算的数字对,但我的猜测是我没有以聪明的方式减少,而且这花费了我的时间.

编辑:假设f(i, j)花时间与j-i计算天真的方式成正比.

Answer 1

您可以使用两个大小的间隔的隐式树:

将有O(log n)表(floor(log_2(n))确切地说),总大小为O(n)(〜2*n).

检索f(i,j)位置i<=j:

retreival最多访问每个表两次,因此运行O(log n).

这可以通过参考`f(i,i + 2 ^(n-1))`表来计算`f(i,i + 2 ^ n)`表来解决.`f(i,i + 2 ^ n)= f(i,i + 2 ^(n-1))+ f(i + 2 ^(n-1),i + 2 ^ n)`.以这种方式计算每个条目需要花费一些时间. (2认同)