在二维数组中查找可被 3 整除的最大路径

Question

给定一个二维数组。

找到“蛇形路径”而：

蛇形路径每行一个元素，相邻两行元素在相邻列
“蛇形路径”的总和需要最大且能被 3 整除（元素本身不一定必须能被 3 整除）

多年来我一直在努力解决这个问题。到目前为止我尝试过的是：

我计算出有 n^3 条潜在的蛇形路径并且每条蛇形路径的长度为 n 然后我只是循环 n^3 条潜在的蛇形路径并检查哪一条具有最大的总和并且是能被 3 整除

问题是这种方法效率不高，它需要 O(n^4)，这很慢，而且这个问题似乎可以使用动态规划来解决。

如有任何帮助，我们将不胜感激

Answer 1

首先I calculated that there are n^3 potential snake paths的说法是错误的，还有很多情况其实是O(2^n)

您可以使用以下动态方法 O(n^2)

At the beginning just keep last row of array and in each step add rows from bottom one by one

In each Step suppose you keep these 3 values for each cell of Current_Array

Max path with SUM % 3 ==0 , Max path with SUM % 3==1 and ...==2

For the new added row, you can easily calculate these 3 parameters from it's bottom row as , for example for index (i,j) just check 3 parameters of (i+1,j+1) and (i+1,j-1) and according to the value of index(i,j)%3 calculate it's parameters

At the end find maximum value of (SUM % 3 ==0) parameter in the array with O(n^2)

Answer 2

我确实发现这是 fiddle 一个有趣的问题。这是一个潜在的解决方案，它将找到如下路径：

Start at index 5 ---v
                    __       
 7   6   5   4   3 | 2|  1    (start)     2
                   '--\ __               
 2   4   6   8  10  12 |14|   (right)  + 14 
                    __ /--' 
 2   7   1   8   2 | 8|  1    (left)   +  8
                __ /--'
 3   1   4   1 | 5|  9   2    (left)   +  5
               '--\ __
 2   3   5   7  11 |13| 17    (right)  + 13
                   '--\ __  
 8   6   7   5   3   0 | 9|   (right)  +  9
                       '--'            ----
                               total:    51

会得到这样的报告：

{path: "RLLRR", startIndex: 5, total: 51}

实现如下所示：

const maxMod3Path = (grid) => 
  [...grid] .reverse () .reduce ((prev, row, ri) => row .map ((c, i) => 
    [
      ...(prev [i - 1] || []).map(({n, p}) => ri == 0 ? {n, p} : ({n, p: 'L' + p})), 
      ...(prev [i + 1] || []).map(({n, p}) => ri == 0 ? {n, p} : ({n, p: 'R' + p})), 
    ] 
      .map (({n, p}) => ({n: n + c, p}))
      .reduce (
        (a, {n, p}) => {a [n % 3] = (n > a [n % 3] .n ? {n, p} : a [n % 3]); return a}, 
        [{n: 0}, {n: 0}, {n: 0}]
      )
    ), 
    grid [0] .map ((c) => [{n: 0, p: ''}, {n: 0, p: ''}, {n: 0, p: ''}])
  ) 
  .map (([{n, p}], startIndex) => ({total: n, path: p, startIndex}))
  .reduce ((a, x) => x.total > a.total ? x : a, {total: 0})

const grid = [
  [ 7,  6,  5,  4,  3,  2,  1 ],
  [ 2,  4,  6,  8, 10, 12, 14 ],
  [ 2,  7,  1,  8,  2,  8,  1 ],
  [ 3,  1,  4,  1,  5,  9,  2 ],
  [ 2,  3,  5,  7, 11, 13, 17 ],
  [ 8,  6,  7,  5,  3,  0,  9 ],
]

console .log (maxMod3Path (grid))

我现在没有时间对这段代码写出很长的解释，但简要说明这是使用动态规划，遵循 Ehsan Gerayli 描述的算法。我们从每行宽度的数组开始，每个条目包含一个包含三个 {n: 0, p: ''} 副本的数组，每个副本用于 0、1 和 2 模数结果3.

从底行开始，我们为每个单元格计算通过从单元格向下和向左或向右移动找到的结果，将总数和路径存储在正确的模数桶中，如果总数大于存储桶的当前值。

最后，我们存储了每个桶的最大值。我们现在可以删除 1 和 2 桶，重命名变量并包括开始的索引。 (.map (([{n, p}], startIndex) => ({total: n, path: p, startIndex})))

这会给我们这样的东西：

[
  {path: "RLRRR", startIndex: 0, total: 24}, 
  {path: "RRRLL", startIndex: 1, total: 39}, 
  {path: "LRRRL", startIndex: 2, total: 27}, 
  {path: "LRRRR", startIndex: 3, total: 45}, 
  {path: "RLRLL", startIndex: 4, total: 42}, 
  {path: "RLLRR", startIndex: 5, total: 51}, 
  {path: "LRLLL", startIndex: 6, total: 39}
]

然后，最后一行的 reduce 调用选择总数最大的一个。

我想我的要求是对的。但是如果一个路径也可以直线下降，你也可以在明显的地方添加：

      ...(prev [  i  ] || []).map(({n, p}) => ri == 0 ? {n, p} : ({n, p: 'D' + p})),

现在将产生结果

{path: "RRDRD", startIndex: 3, total: 57}

最后，如果您的网格可以包含负数，那么您应该将所有 {n: 0} 个实例替换为 {n: -Infinity}。（这还没有经过全面测试，但看起来它会起作用。）

我想听听这是否符合要求。

在二维数组中查找可被 3 整除的最大路径

Find Maximum Path thats divisible by 3 in 2D array

javascript

arrays

algorithm

dynamic-programming

graph-algorithm