如何在r×c矩阵中放置1×2/2×1瓷砖以最大化覆盖单元格总和？

这个问题本质是最大权匹配问题，可以通过二分图建模、动态规划或者网络流三种核心思路解决，具体选择取决于矩阵的规模和结构：

核心思路：二分图最大权匹配 #

把矩阵每个单元格当成节点，相邻（上下左右）单元格之间连一条边，边的权重是两个单元格的数值和。我们要选一组不重叠的边（即没有共享节点），让总权重最大——这就是标准的二分图最大权匹配问题。

建模细节 #

• 按单元格坐标i+j的奇偶性分成两个集合：坐标和为偶数的放集合A，奇数的放集合B。相邻单元格必然分属不同集合，天然形成二分图。
• 给每对相邻单元格加一条边，权重为两数之和，然后跑最大权匹配算法即可得到最优解。

具体实现方案 #

1. KM算法（通用解法） #

KM是解决二分图最大权匹配的经典算法，适合绝大多数规模的矩阵。实现时：

• 先构建邻接表或邻接矩阵存储边权。
• 区分二分图的左右集合，套用KM算法模板即可得到最大匹配的总权重，也就是最优覆盖的数值总和。

2. 动态规划（小规模/特殊结构矩阵） #

如果矩阵是单行、单列或者2×c这类简单结构，动态规划效率更高：

• 单行矩阵：类似打家劫舍问题，定义dp[i]为前i个单元格的最大总和。状态转移：
  dp[i] = max(dp[i-1], dp[i-2] + matrix[0][i-2] + matrix[0][i-1])
  边界：dp[0]=0，dp[1]=0，dp[2]=matrix[0][0]+matrix[0][1]
• 2×c矩阵：可以定义dp[i][s]表示处理到第i列，状态s（比如0=两格都不覆盖，1=上格覆盖，2=下格覆盖，3=两格都覆盖）下的最大总和，然后按列转移状态。

3. 网络流最小割转化 #

把问题转成最小割问题求解，思路是：

• 建源点S、汇点T，S连所有A集合节点（权重为单元格数值），B集合节点连T（权重为单元格数值）。
• 相邻A、B节点之间连双向无穷大边。
• 计算S到T的最小割，所有单元格数值总和减去最小割就是最大覆盖总和——因为最小割对应的是我们放弃覆盖的单元格，总和减去它就是最优解。

示例代码（单行矩阵动态规划） #

def max_tile_sum_single_row(matrix):
    row = matrix[0]
    n = len(row)
    if n < 2:
        return 0
    dp = [0] * (n + 1)
    dp[2] = row[0] + row[1]
    for i in range(3, n+1):
        dp[i] = max(dp[i-1], dp[i-2] + row[i-2] + row[i-1])
    return dp[n]

# 测试用例
test_matrix = [[1, 2, 3, 4]]
print(max_tile_sum_single_row(test_matrix))  # 输出6（选择2+4）

关键注意点 #

• 如果矩阵里有负数，算法会自动跳过覆盖这些负数单元格的组合，保证总和最大。
• 当单元格总数为奇数时，必然有一个单元格无法被覆盖，算法会自动选择放弃数值最小的那个，让整体总和最大。

内容的提问来源于stack exchange，提问作者bigtree