在 rxc 矩阵上放置 1x2 或 2x1 块，以实现覆盖单元的最大总和

考虑位置(n, k)，我们有 3 种情况：

1. 放置 1 * 2 的瓷砖
2. 放置 2 * 1 的瓷砖
3. 不放置任何内容

例如：

Case 1:
????
????
??xx

Case 2:
????
???x
???x

Case 3:
????
????
???.

对于情况2，我们会记录下一行中哪个格子是我们已经走的，这样就可以通过dp来解答这道题了。

我们可以定义：

sol(x, y, right_incomplete, up_incompletes) 
  is the maximum of point(x, y) in the condition of right_incomplete and up_incomples

因此对于要点(x, y)：

如果right_incomplete（这意味着我们在 中放置 1*2 块瓷砖(x, y+1)），我们必须在 处关闭这块瓷砖(x, y)

如果up_incomplete（这意味着我们在 中放置 2*1 块瓷砖(x+1, y)），我们必须在 处关闭这块瓷砖(x, y)

如果right_incomplete和都为up_incomplete，则表示无可行解。

如果不是且right_incomplete，up_incomplete我们有三个选择：放置 1 * 2、放置 2 * 1 或什么都不做。每个选择都会引出一个较小的问题。

我们举个例子：

红线表示有k网格的 up_incompletes。

蓝线表示正确不完整。

箭头表示不完整，否则表示没有。

现在，我们考虑深灰色网格。根据我们的up_incompletes信息，我们应该在这个网格处关闭这个不完整部分，所以这里我们只有一个选择。

完成这些之后，我们就可以得到：

我们再举一个例子：

由于此网格没有不完整的内容，因此我们有三个选择，分别是：

选择 1，不采取任何行动：

选择 2，放置一个 1 * 2 的瓷砖，这样我们的下一个网格就会有一个 right_incomplete：

选择 3，放置一个 2 * 1 的瓷砖，因此对于同一列的网格下一行将有一个 up_incomplete：

总之：

sol(x, y, right_incomplete, up_incompletes) = 
  max(all_possible_solutions) + take_x_y?array[x][y]:0

通过这种方式，我们就可以找到O(n*k*2^k)解决方案。

您可以查看我的代码以了解更多详细信息：

MAX_ANS = 10**100


def sol(matrix):
    mem = {}

    def _sol(x, y, up_incomplete, right_incomplete):
        p = (x, y, up_incomplete, right_incomplete)
        if up_incomplete[-1] and right_incomplete:
            return -MAX_ANS
        if x == 0 and y == 0:
            if up_incomplete[-1] or right_incomplete:
                return matrix[x][y]
            else:
                return 0
        if mem.get(p) is not None:
            return mem[p]
        ans = 0
        if y != 0:
            next_x, next_y = x, y - 1
        else:
            next_x, next_y = x - 1, len(matrix[0]) - 1

        if right_incomplete:
            new_up_incomplete = tuple([False]) + up_incomplete[:-1]
            ans = max(ans, matrix[x][y] + _sol(next_x, next_y, new_up_incomplete, False))
        elif up_incomplete[-1]:
            new_up_incomplete = tuple([False]) + up_incomplete[:-1]
            ans = max(ans, matrix[x][y] + _sol(next_x, next_y, new_up_incomplete, False))
        else:
            if y != 0:
                new_up_incomplete = tuple([False]) + up_incomplete[:-1]
                ans = max(ans, matrix[x][y] + _sol(next_x, next_y, new_up_incomplete, True))
            if x != 0:
                new_up_incomplete = tuple([True]) + up_incomplete[:-1]
                ans = max(ans, matrix[x][y] + _sol(next_x, next_y, new_up_incomplete, False))

            new_up_incomplete = tuple([False]) + up_incomplete[:-1]
            ans = max(ans, _sol(next_x, next_y, new_up_incomplete, False))

        mem[p] = ans
        return ans

    return _sol(len(matrix) - 1, len(matrix[0]) - 1, tuple([False]*len(matrix[0])), False)


test_1 = [
    [1, 2, 3]
    , [4, -5, -6]
]

test_2 = [
     [2, 6, 3, 1]
    , [6, 5, 6, 1]
    , [2, -6, 2, 1]
]

test_3 = [
     [10, -5]
    , [-5, 2]
]

print(sol(test_1))
print(sol(test_2))
print(sol(test_3))