我们首先创建一个递归关系。令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;
}