algorithm - 如何找到矩阵中的最大 L 和？

Question

这是另一个动态规划问题，在给定矩阵 (mxn) 中找到最大 L(chess horse - 4 item) sum

例如 ：

1 2 3

4 5 6

7 8 9

L : (1,2,3,6), (1,4,5,6), (1,2,5,8), (4,5,6,9) ...

最大的和是 sum(L) = sum(7,8,9,6) = 30

最优解的 O(complexity) 是多少？

看起来像这个问题（最大和的子矩阵）

1. 说所有项目都是正面的

2. 积极的和消极的

欢迎任何想法！

Answer 1

如果您的 L 是恒定大小（如您所说的 4 个元素），只需计算所有 < n*m 位置的总和并找到最大值。重复您可能拥有的 8 个不同方向。总体上是 O(nm)。