如何找到以矩阵的最大大号总和？ [英] how to find the maximum L sum in a matrix?

问题描述

下面是另一个动态规划的问题，找出最大L（国际象棋的马 - 4项）给定矩阵之和（MXN）

here is another dynamic programming problem that find the maximum L(chess horse - 4 item) sum in the given matrix (m x n)

例如：

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）

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

和最大的总和是总和（L）=总和（7,8,9,6）= 30

and the biggest sum is sum(L) = sum(7,8,9,6) = 30

什么是最优解的O（复杂性）？

what is the O(complexity) of the optimal solution ?

它看起来像这样问题（子矩阵最大总和）

1. 说的所有项目都是正

1. Say all items are positive

正反两方面

任何想法，欢迎！

推荐答案

如果你的L是固定的大小（4个元素，像你说的），只计算其总和所有＆LT; N * M的位置，找到最大的之一。重复8个不同的方向，你可以有。这是O（nm）的整体。

If your L is constant size (4 elements, as you say), just compute its sum over all < n*m positions and find the maximum one. Repeat for the 8 different orientations you could have. That's O(nm) overall.

这篇关于如何找到以矩阵的最大大号总和？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！