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

Question

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

例如:

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) 是多少？

看起来像这样problem (submatrix with maximum sum)

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

2. 正反两面

欢迎任何想法!

Answer 1

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