Подсчет возможных путей из левого верхнего угла в правый нижний в матрице M x N путем перемещения вправо, вниз или по диагонали.

Опубликовано: 20 Сентября, 2022

Даны 2 целых числа M и N. Задача состоит в том, чтобы найти количество всех возможных путей из левого верхнего угла в правый нижний в матрице M x N с ограничениями, согласно которым из каждой ячейки вы можете двигаться либо только вправо, либо вниз, либо по диагонали.

Примеры:

Input:  M = 3, N = 3
Output: 13
Explanation: There are 13 paths as follows: VVHH, VHVH, HVVH, DVH, VDH, VHHV, HVHV, DHV, HHVV, HDV, VHD, HVD, and DD where V represents vertical, H represents horizontal, and D represents diagonal paths.

Input:  M = 2, N = 2
Output: 3

Подход: Идея состоит в том, чтобы использовать рекурсию для нахождения общего количества путей. Этот подход очень похож на тот, который обсуждался в этой статье. Выполните следующие шаги, чтобы решить проблему:

  • Если M или N равно 1, вернуть 1.
  • В противном случае создайте рекурсивную функцию numberOfPaths(), вызывающую ту же функцию для значений {M-1, N}, {M, N-1} и {M-1, N-1} , представляющих движение по вертикали, горизонтали и диагонали соответственно.

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


Временная сложность: O(3 M*N )
Вспомогательное пространство: O(1), так как дополнительное пространство не занято.

Эффективный подход : Dp (с использованием мемоизации)

Временная сложность : O(M*N)

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

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