打印长度为 2 到 n+1 的所有可能子序列的元素总和的高效算法
Efficient algorithm to print sum of elements at all possible subsequences of length 2 to n+1
我将从一个例子开始。假设我们有一个大小为 3 的数组，其中包含元素 a、b 和 c，例如：(where a, b和c是一些数值)
|1 | 2| 3|
|a | b| 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
类似地，对于大小为 4 且元素为 a、b、c、d 的数组，输出将为：
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：我的问题与 this 不同，因为：
- 我不需要所有可能的排列。我需要从长度 2 到 n+1 的所有可能递增子序列。
- 我也不需要打印所有可能的此类序列，我只需要由此获得的值（如上所述）因此我正在寻找一些数学概念or/and 一些动态规划方法可以有效地解决这个问题。
- 请注意，我正在根据索引值找到所有可能的此类递增子序列的集合，然后根据上述索引位置处的值进行计算。
作为一个好像消失了的post指出了一种方法是获取递归关系。令 S(n,k) 为长度为 k 的递增子序列（1..n）的总和，该子序列由序列索引的数组元素的乘积。这样的子序列要么以 n 结尾，要么不以 n 结尾；在第一种情况下，它是 1..n-1 和 {n} 的长度为 k-1 的子序列的串联；在第二种情况下，它是长度为 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
我将从一个例子开始。假设我们有一个大小为 3 的数组，其中包含元素 a、b 和 c，例如：(where a, b和c是一些数值)
|1 | 2| 3|
|a | b| 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
类似地，对于大小为 4 且元素为 a、b、c、d 的数组，输出将为：
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：我的问题与 this 不同，因为：
- 我不需要所有可能的排列。我需要从长度 2 到 n+1 的所有可能递增子序列。
- 我也不需要打印所有可能的此类序列，我只需要由此获得的值（如上所述）因此我正在寻找一些数学概念or/and 一些动态规划方法可以有效地解决这个问题。
- 请注意，我正在根据索引值找到所有可能的此类递增子序列的集合，然后根据上述索引位置处的值进行计算。
作为一个好像消失了的post指出了一种方法是获取递归关系。令 S(n,k) 为长度为 k 的递增子序列（1..n）的总和，该子序列由序列索引的数组元素的乘积。这样的子序列要么以 n 结尾，要么不以 n 结尾；在第一种情况下，它是 1..n-1 和 {n} 的长度为 k-1 的子序列的串联；在第二种情况下，它是长度为 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