algorithm - 为多个和找到一个没有除法的算法

Question

我有数量由以下多个和与乘积给出:

哪里 和 是向量，t = 0, 1, ... , N-1。

例如，如果 N = 4，则对应于 i = 2 的数量是

a 和 b 的元素可以任意小。因此，我想避免 split 。问题是我一辈子都做不出一个算法来计算这个，即使是用最直接的方式(尽管速度是个问题所以我想要一个快的)。有什么指点吗？

Answer 1

我认为您可以使用动态规划在 O(t.N) 周期内计算它。

这个想法是计算一个数量 f(i,t,n)，它与您的 e(i,t) 完全相同，除了第一个总和将 N 替换为 n。

如果 t==0，我们定义 f(i,t,0) 为 1，否则为 0。

我们可以通过考虑索引 n 处的位置是“a”、“b”还是跳过的情况，根据先前的值计算 f(i,t,n)。

If n==i
    f(i,t,n)=f(i,t,n-1)
else
    f(i,t,n)=f(i,t,n-1).a_n+f(i,t-1,n-1).b_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