0

这是我关于最大 L 总和的第一个问题，这是它的不同且困难的版本。

问题：给定一个mxn 正整数矩阵，求从第 1 行到第m 行的最小 L 和。L(4项)喜欢象棋马步

示例：M = 3x3

0 1 2

1 3 2

4 2 1

可能的 L 步是：(0 1 2 2), (0 1 3 2) (0 1 4 2) 我们应该从第 1行到第3行，总和最小

我用动态编程解决了这个问题，这是我的算法：

1.取一个mxn另一个Minimum L Moves Sum数组并复制主矩阵的第一行。我称之为（MLMS） 2.从第一个单元格开始，向上查找 L 移动并计算它
3.如果它小于存在值，则将其插入 MLMS
4.执行步骤 2. 直到第 m行
5.选择最小值在第m行求和

让我逐步解释我的示例：

  1. M[ 0 ][ 0 ] sum(L1 = (0, 1, 2, 2)) = 5 ; 总和（L2 =（0,1,3,2））= 6；所以 MLMS[ 0 ][ 1 ] = 6
    sum(L3 = (0, 1, 3, 2)) = 6 ; 总和（L4 =（0,1,4,2））= 7；所以 MLMS[ 2 ][ 1 ] = 6

  2. M[ 0 ][ 1 ]总和（L5 = (1, 0, 1, 4)) = 6; 总和（L6 =（1,3,2,4））= 10；所以 MLMS[ 2 ][ 2 ] = 6

    ... 最后一个 MSLS 是：
    0 1 2
    4 3 6
    6 6 6
    这意味着 6 是从 0 到 m 可以达到的最小 L 和。

我认为它是O(8*(m-1) n) = O(m n)。是否有适合此问题的最佳解决方案或动态规划算法？

谢谢，对不起，很长的问题

4

1 回答 1

1

总行数的矩阵中如何同时存在0-th和行？m-thm

无论如何，一个简单的Dijkstra将为您提供最佳路径O(n*m)（假设您有一个良好的数据结构可以在尚未到达的点列表中找到最小值）。

此外，如果您的马只能在棋盘上向下移动（有时向上移动以减少总路径权重很有用），您可以编写简单的 DP。只需从棋盘底部开始，为每个位置计算到达底部所需的时间。由于您可以从每个位置最多进行 4 次移动，因此这是一个简单的最小值检查。像这样的东西

for (int row = m - 1; row >= 0; --row) {
    for (int col = 0; col < m; ++col) {
        int path1 = a[row][col + 1] + a[row][col + 2] + a[row + 1][col + 2] + best[row + 1][col + 2];
        int path2 = a[row][col + 1] + a[row + 1][col + 1] + a[row + 2][col + 1] + best[row + 2][col + 1];
        int path3 = ...
        int path4 = ...
        best[row][col] = min(path1, path2, path3, path4);
    }
}

编辑
为什么要上去？想象一下这样的矩阵（这*意味着一些非常大的数字，比如 1000000000）。很明显，你必须先从(0, 0)棋盘的右边走，然后再走下去。

111111111111
111111111111
*********111
*********111

所以，路径看起来像这样

...1...1...1
11...1...1..
*********11.
*********11.
于 2010-12-23T13:57:00.280 回答