c++ - 减少数组的最大最小和 2 分区的时间复杂度

Question

让array[N] N 的数组非负值。我们试图递归地将数组分成两 (2) 个子数组，以便我们可以实现每个子数组的最大“最小和”。该解决方案由以下递归描述:

我们要计算opt[0][N-1] .

让c[x][y]表示 sum{array[i]}来自 x最多 y (包含)。我已经设法使用动态编程在以下 C++ 代码片段中展开递归:

for ( uint16_t K1 = 0; K1 < N; K1 ++ ) {
    for ( uint16_t K2 = 0; K2 < N-K1; K2 ++ ) {

        const uint16_t x = K2, y = K2 + K1;
        opt[x][y] = 0;

        for ( uint16_t w = x; w < y; w ++ ) {

            uint32_t left  = c[x][w]   + opt[x][w];
            uint32_t right = c[w+1][y] + opt[w+1][y];

            /* Choose minimum between left-right */
            uint32_t val = MIN( left, right );

            /* Best opt[x][y] ? */
            if ( val > opt[x][y] ) {
                opt[x][y] = val;
            }
        }

    } /* K2 */
}     /* K1 */

此技术解析所有子数组，从大小 1 开始最大尺寸 N .因此，最终解决方案将存储在 opt[0][N-1] 中。 .

例如，如果 N=6 ，矩阵将迭代如下:(0,0) (1,1) (2,2) (3,3) (4,4) (5,5) (0,1) (1,2) (2,3) (3,4) (4,5) (0,2) (1,3) (2,4) (3,5) (0,3) (1,4) (2,5) (0,4) (1,5) (0,5) .最终答案将在 opt[0][5] 中.

我已经测试并验证了上述技术可以展开递归。我试图进一步降低复杂性，因为如果我是正确的话，这将在 O(n^3) 中运行。这能实现吗？

---

编辑:我还注意到递归的物理意义，正如评论中所问的那样。让N表示 N一条直线上的城市。我们是控制这些城市的地主；在一年的年底，每个城市i支付 array[i] 的维护费硬币，只要它在我们的控制之下。

我们的城市正受到优势力量的攻击，失败在所难免。每年年初，我们都会在两个相邻的城市之间竖起一堵墙i , i+1 , x <= i <= y .每年，敌军都会从西方进攻，从而征服所有城市 [x,i] , 或将从东方进攻，从而征服 [i+1,y] 的所有城市.其余城市将在年底向我们支付维护费用。敌军于年底毁墙退却，次年又发动新的进攻。当只剩下 1 个城市时游戏结束。

敌军总是会从最佳位置进攻，以随着时间的推移减少我们的最大收入。我们的策略是选择墙的最佳位置，从而在游戏结束时最大化我们的总收入。

Answer 1

根据 @NiklasB. 的贡献，这是问题的最终答案。让w(x,y)表示问题的数组的最佳划分 opt[x][y] .如下，x <= w(x,y) < y .我们假设所有子问题的位置 opt[x][y]具有给定的子数组大小 d = y-x是已知的。

现在让我们尝试找到最优的 w所有大小为 k+1 的子问题的位置.我们可以很容易地证明 w(x,y+1) >= w(x,y) ; IOW 如果我们向右添加另一个元素，最佳分区可能会“向右移动”，以便更均匀地平衡两个总和；但是它不能“向左移动”。以类似的方式，w(x-1,y) <= w(x,y) .

注意:如果有人可以尝试从数学上验证上述内容，那将会很有帮助。

如下，设wall[x][y]表示最优 w子问题的解决方案 opt[x][y] .循环 for ( uint16_t w = x; w < y; w ++ )在原始代码段中，将修改如下:

for ( uint16_t w = wall[x][y-1]; w <= wall[x+1][y]; w ++ ) {
  ...
  if ( val > opt[x][y] ) {
    opt[x][y] = val;
    wall[x][y] = w;
  }
}

需要进行一些修改以处理 0 <= y-x <= 1 时的极端情况，但它完成了工作。它将运行时间复杂度从 O(n^3) 降低到 O(n^2)，因为通过考虑 w，计算较大子问题的解决方案的时间被摊销为 O(1)界限。示例:使用 N = 2500 ，递归算法(带内存)在 58 秒内运行。 O(n^2) 算法运行仅需 148 毫秒。