0

这是另一个动态规划问题,在给定矩阵 (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. 积极的和消极的

欢迎任何想法!

4

1 回答 1

5

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

于 2010-12-21T16:56:04.857 回答