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

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 statesO(N*K)。通过我上面提到的技巧，内存可以是 O(K) 。