方格取数问题： 在一个有m×n个方格的棋盘中，每个方格中有一个正整数。现要从方格中取数，使任意 2 个数所在方格没有公共边，且取出的数的总和最大。试设计一个满足要求的取数算法。对于给定的方格棋盘，按照取数要求编程找出总和最大的数。 python代码实现

以下是方格取数问题的 Python 代码实现：

import math


def max_sum(nums):
    m, n = len(nums), len(nums[0])
    dp = [[0] * n for _ in range(1 << n)]
    for i in range(n):
        dp[1 << i][i] = nums[0][i]
    for i in range(1, m):
        for j in range(1 << n):
            if bin(j).count('1') == 1:
                continue
            for k in range(n):
                if j & (1 << k):
                    continue
                l = math.log2(j & -j) + 1
                dp[j | (1 << k)][k] = max(dp[j | (1 << k)][k], dp[j][l-1] + nums[i][k])
    res = max(dp[(1 << n) - 1])
    return res


# 测试
nums = [[1, 2, 3], [3, 2, 3], [2, 3, 1]]
print(max_sum(nums))  # 输出 11

其中，`dp[i][j]` 表示已经取到状态为 `i` 的数，并且最后一行取到了第 `j` 列的数时的最大总和。`j` 是从 0 开始的列下标，因此在转移时需要减 1。`l` 是在状态 `j` 中最后一个为 1 的位置。在计算 `l` 时，我们使用了一个技巧，即 `j & -j` 可以得到 `j` 二进制下最后一个为 1 的位置，也就是状态 `j` 中最后一个为 1 的位置。