2

我将从一个例子开始。假设我们有一个大小为3的数组，其中包含元素a，例如：（其中b和是一些数值）cabc

|1 | 2| 3|
|一个 | 乙| c|

（假设索引从 1 开始，如上例所示）

现在所有可能增加的长度为2的子序列是：

12 23 13

所以需要这些索引处元素的乘积之和，即ab+bc+ac

对于长度3，我们只有一个递增的子序列，即 123，因此abc应该打印。
对于长度4，我们没有序列，因此0打印并且程序终止。

所以给定数组的输出将是：

ab+bc+ac,abc,0

因此，例如，如果元素a和b分别c是 1、2 和 3，那么输出应该是11,6,0

同样，对于具有元素 a、b、c、d 的大小为4的数组，输出将是：

ab+ac+ad+bc+bd+cd,abc+abd+acd+bcd,abcd,0

等等...

现在显然蛮力对于较大的数组大小值来说效率太低了。我想知道是否有一种有效的算法来计算给定大小的数组的输出？

编辑1：我尝试找到一种模式。例如对于大小为4的数组：

The first value we need is :(ab+ac+bc)+d(a+b+c)= ab+ac+ad+bc+bd+cd (Take A=ab+ac+bd) then the second value we need is:(abc) +d(A) = abc+abd+acd+bcd(B=abc) then the third value we need is : (0) +d(B) = abcd(Let's take 0 as C) then the fourth value we need is: +d(C) = 0

但它仍然需要大量计算，我无法找到一种有效的方法来实现它。

编辑2：我的问题与此不同，因为：

  1. 我不需要所有可能的排列。我需要从长度 2 到 n+1 的所有可能增加的子序列。
  2. 我也不需要打印所有可能的此类序列，我只需要由此获得的值（如上所述），因此我正在寻找一些数学概念或/和一些动态编程方法来有效地解决这个问题。
  3. 请注意，我正在根据索引值找到所有可能的此类递增子序列的集合，然后根据上述索引位置处的值进行计算。
4

1 回答 1

0

正如一篇似乎已经消失的帖子所指出的，一种方法是获得递归关系。令 S(n,k) 是序列索引的数组元素的乘积的长度为 k 的递增子序列（1..n）的总和。这样的子序列要么以 n 结尾，要么不以 n 结尾；在第一种情况下，它是长度为 k-1 的 1..n-1 和 {n} 的子序列的串联；在第二种情况下，它是长度为 k 的 1..n-1 的子序列。因此：

S(n,k) = S(n-1,k) + A[n] * S(n-1,k-1)

为此，我们需要添加：

S(n,0) = 1
S(n,m) = 0 for m>n
于 2015-10-07T10:23:32.300 回答