如何获得 Nx3 矩阵中 k 2x1 或 1x2 块的最大总和

Question

我有一个 N x 3 矩阵和 int 值的问题。我需要用 K 个 2x1 或 1x2 的瓷砖拼贴它，这样它们就不会重叠，并且我可以通过使用动态编程获得最大的总和。解决此类问题的最佳方法是什么？

Example 5 x 3 matrix, K = 5: 

2 6 2
6 5 6
2 6 2 
1 1 1
1 1 1

Good tiles: (6,2), (6,2), (6,2), (6,5), (2,1)
Result = 38

还有一个边缘案例的例子：

2 x 3 Matrix, K = 2

0 4 1
3 4 1

Good tiles: (4,1), (4,3)
Result = 12

Answer 1

让我们将一行的状态定义为被一些 K 砖块覆盖的单元格。你有 8 种组合 (2^3)，从 000（一切都没有被覆盖）到 111（一切都被覆盖）（你可以使用二进制来编码状态以提高效率）。

动态规划矩阵将为a[row][tiles][state]。其中 row 是我们正在处理的 row，从上到下，tiles 是您已经放置了多少块，state 是我们上面定义的状态，值是当前最大值总和

为了填充它，我们从上到下。我们通过仅允许将垂直磁贴放置在当前和上方（而不是下方）的行上来简化事情。您可以遍历行之间的图块放置组合（有些是互斥的）。当前行有 3 个垂直选项和 2 个水平选项（5 个选项，总共 12 种组合，如果我算对的话）。还遍历 'titles' 的可能值。对于每个组合，寻找所有可能的组合，允许它放置在前一行（以便垂直瓷砖不重叠）取最大值并更新动态矩阵。有些组合非常严格（3 个垂直方块需要上一行中的 000），而一些则非常宽松（1 个水平方块允许所有可能性）。在纸上多做几次，看看效果如何。

作为优化注意事项，您只需要知道前一行的值，因为上面的值不会考虑在内，因此您可以只保留前一行和当前行。

算法应该是这样的

For  i from 0 to N
   for tiles from 0 to K
      for each combination
        if tiles - combination.tiles < 0: continue
        m = -1
        for each state compatible with combination.previous_row
          m = max(m, a[i-1][tiles - combination.tiles][state])
        if m > 0
          a[i][tiles][combination.state] = max(a[i][tiles][combination.state], m)

解是最后一行状态之间的最大值 tiles=K。

复杂度将是 N*K* 12 combinations * 2^3 states，所以 O(N*K)。使用我上面提到的技巧，内存可以是 O(K)。

如何获得 Nx3 矩阵中 k 2x1 或 1x2 块的最大总和

How to get max sum of k 2x1 or 1x2 tiles in Nx3 matrix

algorithm

dynamic-programming