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

Question

如何通过在矩阵 rxc 中最佳放置图块来找到最大可能的值之和，其中每个单元格都有一个整数值？

目标是通过用 1x2 或 2x1 块覆盖单元格来最大化总和。

For example:
k = 2, n = 3
Matrix:
1 2 3
4 -5 -6
The max sum is 10 
Good tiles: (1,4) and (2,3)

Answer 1

考虑地点

(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

（这意味着我们在

(x, y+1)

中放置了1*2块），我们必须在

(x, y)

关闭这个块

如果

up_incomplete

（这意味着我们在

(x+1, y)

中放置了2*1个图块），我们必须在

(x, y)

关闭这个图块

如果

right_incomplete

和

up_incomplete

同时存在，则表示没有可行解。

如果不是

right_incomplete

和

up_incomplete

，我们有三种选择：放置1 * 2，放置2 * 1，或者什么都不做。每一个选择，我们都会遇到一个更小的问题。

我们举个例子：

红线表示具有

k

网格的 up_incompletes。

蓝线表示右边_不完整。

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

现在，我们正在考虑深灰色网格。根据我们的

up_incompletes

信息，我们应该在这个网格处关闭这个不完整的部分，所以我们这里只有 1 个选择。

完成之后，我们会：

我们再举个例子：

由于这个网格没有不完整的地方，所以我们有三个选择，分别是：

选择 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))