algorithm - 如何在 Nx3 矩阵中获得 k 个 2x1 或 1x2 block 的最大总和

Question

我有一个问题，我有一个带有 int 值的 N x 3 矩阵。我需要用 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)。