Максимизируйте ценность монет, когда монеты из соседних строк и столбцов не могут быть собраны

Опубликовано: 27 Февраля, 2023

Учитывая двумерный массив arr[][] размера N * M , значение в arr[][] представляет стоимость монет, задача состоит в том, чтобы максимизировать стоимость собранных монет, когда во время сбора монет из arr[][ ] , все монеты из соседнего ряда (т.е. i – 1 и i + 1) исчезнут, а монеты в соседнем столбце (т.е. arr[i][j + 1] и arr[i][j – 1] ) также исчезнет.

Примеры:

Input: arr[][] = {{2, 7, 6, 5}, {9, 9, 1, 2}, {3, 8, 1, 5}}
Output: 25
Explanation: Collect coin 7, 5, from row 1 and 8 and 5 from row 3.

Input: arr[][] = {{12, 7, 6, 5}, {9, 9, 3, 1}, {9, 8, 1, 2}}
Output: 29

Подход с использованием динамического программирования:

This problem is composed of multiple smaller subproblems. 

  • First subproblem is that if we somehow know the maximum value of coins collected by each row by following the condition that no two consecutive cell in each of the rows (i.e, arr[i][j + 1] and arr[i][j – 1]) would be collected at the same time. We’ll store this subproblem in some other array and 
  • Again we have to follow the other constraint of the problem that coins can’t be collected in adjacent row. 

And to solve this constraint we’ll again use the similar technique that we used before to find the result.

Выполните следующие шаги, чтобы реализовать вышеуказанную идею:

  • Переберите каждую строку и вызовите рекурсивную функцию (скажем, findMax ), чтобы найти максимальное количество монет, которые можно собрать в каждой строке, следуя ограничению, согласно которому монеты в соседнем столбце не могут быть собраны.
  • Сохраните приведенный выше результат в массиве (скажем, dp[] ).
  • Снова вызовите функцию findMax для состояния, хранящегося в массиве dp[] , чтобы найти максимальное значение, которое может быть собрано среди всех строк, учитывая, что монеты в соседних строках не могут быть собраны.

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(N * M), где N — количество строк, а M — количество столбцов.
Вспомогательное пространство: O(max(N, M))

РЕКОМЕНДУЕМЫЕ СТАТЬИ