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

Question

如何通过优化放置图块来找到最大可能的值之和？

给定一个 k × n 矩阵，其中每个单元格包含一个整数值（范围从 -10^6 到 10^6），如何放置 1x2 或 2x1 瓷砖，以便：

• 您放置尽可能多的图块，以最大化覆盖单元格上的值的总和。
• 每个图块恰好覆盖两个相邻的单元格，并且没有单元格被超过一个图块覆盖。 网格尺寸受限于 1 <= k <= 10 and
  1 <= n <= 1000.

For example:
k = 2, n = 3
Matrix:
1 2 3
4 -5 -6
The answer would be 10, 
Good tiles: (1,4) and (2,3)

For example 2:
k = 3, n = 4
Matrix:
2 6 3 1
6 5 6 1
2 -6 2 1
The answer would be 34.
One possible optimal placement istiles: (2,6),(2,6),(5,6),(3,1),(2,1)

我尝试使用暴力方法，但时间太长。我相信最好的解决方案的复杂度可能约为 O(n*k*2^k)。

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

您可以查看我的代码了解详情：

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