我有一个问题，其中有一个具有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
让我们将一行的状态定义为被一些K块覆盖的单元格。您有8个组合(2^3(，从000(所有内容都未覆盖(到111(所有内容均已覆盖((您可以使用二进制对状态进行编码以提高效率(。
动态编程矩阵将为a[row][tiles][state]。其中，row是我们正在处理的row，从上到下，tiles是您已经放置的瓷砖数量，state是我们上面定义的状态，值是当前的最大和。
为了填满它，我们从上到下。我们通过只允许在当前和上面(而不是下面(的行上放置一个垂直平铺来简化事情。您可以迭代行之间的平铺放置组合(有些是互斥的(。当前行上有3个垂直选项和2个水平选项(如果我计算正确的话，总共有5个选项，共12个组合(。还要遍历"title"的可能值。对于每个组合，寻找所有可能的组合，这些组合允许将其放置在前一行(这样垂直瓦片就不会重叠(，并获取最大值并更新动态矩阵。有些组合非常严格(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(。