在数组中获取N个最小连续块

Question

我目前正在解决以下问题:

给定一个M个正数的数组,我需要得到N个具有一定长度的连续数字块.例如,当我有数组时:

6 9 3 2 8 1 6 9 7

当我需要找到一个长度为3的块时,解决方案是[3,2,8],它的最小总和为13.当我需要找到两个块时,算法应该给出[3,2,8]和[1,6,9]因为这些块中所有元素的总和是最小的(29).假设序列的长度总是严格大于块长度的N倍(因此始终存在解决方案).

我认为这个问题可以通过使用DP解决,但我目前看不出如何.我很难找到子问题之间的经常性关系.有人能帮我一把吗？

提前致谢!

Answer 1

1. 计算具有给定长度的每个块的总和,并使用初始索引记录它们.这可以通过复杂性来完成O(n).所以你得到一个像这样的列表:

   index    sum
   0        18
   1        14
   2        13
   ...      ...
   

2. 由于目标块不能相互重叠,因此它们的索引的每个差异都不能小于给定的长度.因此,您需要在列表中应用简单的动态规划算法.

   如果块长度是l,列表长度是n(比如列表S[n]),并且你想找到m块,那么

   F(n,m,l) = min { F(n-i-l,m-1,l) + S[n-i] } (for i = 0 ~ n-(m-1)*l)

在这一步的复杂性是O(nm)哪里m是你要多少块.

最后,复杂性是O(nm).如果您需要更多详细信息,请告诉我们.