减少阵列的最大最小和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].剩下的城市将在年底向我们支付保养费.敌军在年底摧毁了城墙,撤退,并在次年发动新的攻击.当只剩下一个城市时,游戏结束.

敌人将始终从最佳位置进攻,以便随着时间的推移减少我们的最大收入.我们的策略是选择最佳位置,以便在游戏结束时最大化我们的总收入.

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]最优解。原始代码片段中的循环将修改如下：wopt[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)，因为通过考虑边界，计算较大子问题的解决方案的时间被摊销为 O(1) w。示例：对于N = 2500，递归算法（带记忆）在 58 秒内运行。O(n^2) 算法的运行时间仅为 148 毫秒。