algorithm - 行列の最大 L 合計を見つける方法は?

Question

これは、指定された行列 (mxn) で最大の L(チェスの馬 - 4 アイテム) の合計を見つける別の動的計画問題です。

例えば ​​：

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(複雑さ) は?

この問題のようです（最大合計の部分行列）

1. すべての項目が正であると言う

2. ポジティブにもネガティブにも

どんなアイデアでも大歓迎です！

Answer 1

あなたの L が一定のサイズ（あなたが言うように4要素）の場合、すべての< n * m位置の合計を計算し、最大のものを見つけてください。8 つの異なる向きについて繰り返します。それは全体でO（nm）です。