algorithm - 分割矩阵

Question

给定一个 N x N矩阵，其中 N <= 25 , 并且每个单元格都有一个正整数值，你怎么能用最多 K 行(用直线上/下直线或直线左/右直线 [注意:它们必须从一侧延伸到另一侧])来划分它，以便最大值组(由分区确定)是最小值？

例如，给定以下矩阵

1 1 2
1 1 2 
2 2 4

我们可以使用 2 条线来划分它，我们应该在第 2 列和第 3 列之间画一条线，以及在第 2 行和第 3 行之间画一条线，这给出了最小化的最大值 4。

我的第一个想法是一个代表每行状态的位掩码，用 2 个整数来代表它。然而，这太慢了。我认为复杂度是 O(2^(2N))也许您可以解决行问题，然后解决列问题？

有人有什么想法吗？

编辑:这是我用谷歌搜索后的问题:http://www.sciencedirect.com/science/article/pii/0166218X94001546

另一篇论文:http://cis.poly.edu/suel/papers/pxp.pdf

我正在努力阅读它^

Answer 1

可以对垂直线尝试所有子集，然后对水平线做动态规划。

假设您已将垂直线集固定为 S。将由矩阵的前 K 行和固定垂直线集 S 组成的子问题的答案表示为 D(K, S)。然后找到一个递归来解决具有更小规模的子问题的 D(K, S) 是微不足道的。

如果您在开始时预先计算每个子矩阵的大小，则总体复杂度应为 O(2^N * N^2)。