我们首先创建一个递归关系。令
f(n, k)为length的子数组与length
k的数组
a的所有乘积之和
n。基本情况很简单：
f(0, k) = 0 for all kf(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;}
