Максимальное количество баллов при переходе от левого верхнего угла Матрицы к правому нижнему углу двумя людьми.

Дана матрица grid[][] порядка N*M с номерами 0-9 в ячейках. Задача состоит в том, чтобы найти максимальную сумму денег, которую можно собрать, когда два человека переместятся из (0, 0) в (N-1, M-1) , двигаясь только вправо и вниз . Если оба человека находятся в одной ячейке, то только один из них может забрать деньги в этом месте.

Примеры:

Input: 
1 1 1 
1 0 1 
1 1 1
Output: 8
Explanation: Let 1 denote the places where person 1 collects the money and 2 denote where person 2 does so, then a possible solution is
1 1 1
2 0 1
2 2 1

Input: 
0 9 9 3 3 
2 9 3 3 3 
0 3 3 3 3 
4 1 1 1 1
Output: 52

Подход: проблема может быть решена с помощью рекурсии, перемещая обоих людей вниз и вправо в каждой из ячеек и находя максимальную сумму путей на всех путях от (0, 0) до (N-1, M-1 ). Итак, идея состоит в том, чтобы найти стоимость всех возможных путей и найти их максимум.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(2 ^N * 2 ^M )
Вспомогательное пространство: O((N*M) ² )