arrays - 在数字数组中获取 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)。如果您需要更多详细信息，请告诉我。