查找没有分裂的算法为多个总和

Question

我具有由下述多重总和和乘积给出一个量：

其中和是向量和t = 0，1，。 ..，N-1。

作为一个例子，如果对应于I N = 4个的数量= 2是

的a和b中的元素可以任意小。正因为如此，我想避免分裂。问题是，我不能为我的生活做一个算法，即使以最直接的方式计算（尽管速度是一个问题，所以我想快速的一个）。任何指针？

Answer 1

我想你可以使用动态规划在O（t.N）周期内计算出它。

这个想法是计算一个与你的e（i，t）完全相同的数量f（i，t，n），除了第一个和已经被n替换为n。

如果t == 0，我们定义f（i，t，0）为1，否则为0。

我们可以通过考虑位于索引n的位置是“a”，“b”还是跳过的情况，根据以前的值计算f（i，t，n）。答案由e（i，t）= f（i，t，N）给出。

我们将为每个t和n的选择计算中间值，因此总体复杂度为O（tN）。

例如，

f(2,0,1) = a_1 
f(2,0,2) = a_1.a_2 
f(2,0,3) = a_1.a_2.a_3 
f(2,1,1) = b_1 
f(2,1,2) = f(2,1,1).a_2 + f(2,0,1).b_2 = b_1.a_2+a_1.b_2