Блог

Задан двумерный массив чисел.

Найдите «змеиный путь», тогда как:

• В змеином пути должен быть элемент в каждой строке, а в двух соседних строках элементы находятся в соседних столбцах
• Сумма «змеиного пути» должна быть максимальной и делиться на 3 (сами элементы необязательно должны быть кратны 3)

Я пытался решить этот вопрос целую вечность. То, что я пробовал до сих пор, это:

Я подсчитал, что существует n ^ 3 потенциальных змеиных пути, а длина каждого змеиного пути равна n, а затем я бы просто перебрал n ^ 3 потенциальных змеиных пути и проверил, какой из них имеет максимальную сумму и делится на 3.

Проблема в том, что этот подход не настолько эффективен, он займет O (n ^ 4), что довольно медленно, и эта проблема, похоже, может быть решена с помощью динамического программирования.

Любая помощь будет с благодарностью

Я нашел это интересной проблемой для решения. Вот потенциальное решение, которое найдет путь, подобный следующему:

 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)) 

Сейчас у меня нет времени писать длинное объяснение этого кода, но краткий обзор заключается в том, что это использует динамическое программирование, следуя алгоритму, описанному Эхсаном Герайли. Мы начинаем с массива шириной каждой строки, каждая запись которого содержит массив из трех копий {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} . (Это не было тщательно протестировано, но похоже, что это сработает.)

Я хотел бы услышать, соответствует ли это требованиям.

Прежде всего, утверждение I calculated that there are n^3 potential snake paths неверно, ситуаций намного больше, и на самом деле это O(2^n)

Вы можете использовать следующий динамический подход, который O(n^2)

• В начале просто сохраните последнюю строку массива и на каждом шаге добавляйте строки снизу одну за другой
• На каждом шаге предположим, что вы сохраняете эти 3 значения для каждой ячейки Current_Array
  • Максимальный путь с СУММОЙ % 3 == 0, максимальный путь с СУММОЙ % 3 == 1 и … == 2
  • Для новой добавленной строки вы можете легко вычислить эти 3 параметра из нижней строки, например, для index (i, j) просто проверьте 3 параметра (i 1,j 1) и (i 1,j-1) и в соответствии со значением index(i, j)%3 вычисляет его параметры
• В конце найдите максимальное значение параметра (SUM % 3 ==0) в массиве с O (n ^ 2)