小编典典

长度为k的所有子数组的元素的乘积和

algorithm

给出了长度为 n 的数组。查找子数组元素的乘积之和。

说明

数组 A* = 长度 3的 [2,3,4]*

长度为 2的 子数组= [2,3],[3,4],[2,4]

[2,3] 中元素的乘积= 6

[3,4] 中元素的乘积= 12

[2,4] 中元素的乘积= 8

长度 2 = 6 + 12 + 8 = 26的子数组的总和

同样,对于长度 3 ,Sum = 24

因此,乘积以模 1000000007 计算的子数组的长度可能更大。

找到所有可能长度(即1、2、3,......,n)的子数组的和的有效方法是什么,其中 n 是数组的长度。


阅读 415

收藏
2020-07-28

共1个答案

小编典典

我们首先创建一个递归关系。令f(n, k)为length的子数组与length k的数组a的所有乘积之和n。基本情况很简单:

f(0, k) = 0 for all k
f(n, 0) = 1 for all n

第二个规则似乎有点违反直觉,但是1是乘法的零元素。

现在我们找到的递归关系f(n+1, k)。我们想要size的所有子数组的乘积k。这里有两种类型的子数组:包含的子数组a[n+1]和不包含的子数组a[n+1]。不包括在内的总和a[n+1]就是f(n, k)。所包含a[n+1]的恰好是所有长度加k-1在一起的子数组a[n+1],因此它们的总和为a[n+1] * f(n, k-1)

这样就完成了我们的重复关系:

f(n, k) = 0                               if n = 0
        = 1                               if k = 0
        = f(n-1, k) + a[n] * f(n-1, k-1)  otherwise

您可以使用巧妙的技巧在动态编程中使用非常有限的内存,因为函数f仅取决于两个较早的值:

int[] compute(int[] a) {
    int N = a.length;
    int[] f = int[N];
    f[0] = 1;

    for (int n = 1; n < N; n++) {
        for (int k = n; k >= 1; k--) {
            f[k] = (f[k] + a[n] * f[k-1]) % 1000000007;
        }
    }

    return f;
}
2020-07-28