Написание рекурсивного алгоритма с динамическим программированием

Question

Я хочу написать алгоритм, использующий технику динамического программирования, который выполняет следующее: Находит количество монотонных путей по краям сетки с n × n квадратными ячейками, которые не проходят выше диагонали.Монотонный путь - это путь, который начинается в нижнем левом углу, заканчивается в верхнем правом углу и полностью состоит из ребер, направленных вправо или вверх.

У меня были некоторые идеи, но я не могу понять, как это сделатьэто правильно.

Answer 1

Сначала найдите базу для своей рекурсии, решив вырожденный случай (сетка 0 x 0).Затем найдите повторяющийся шаг, представив, что часть проблемы, скажем, K x M уже решена, и посмотрите, сможете ли вы расширить это решение, добавив к нему одну строку или один столбец, сделав решение K+1 x M или K x M+1.Это должно быть просто: для каждой добавляемой точки посмотрите, находится ли точка сетки ниже диагонали, а затем сложите количество путей, ведущих к этой точке снизу и слева.Одна из этих точек будет в K x M, другая - в дополнительной строке или столбце, который вы строите.

С вырожденным случаем и рекурсивным шагом в руках, постройте свое решение, сначала решивпроблема 0 x N, затем 1 x N, затем 2 x N и т. д., пока не будет найдено решение N x N.

Answer 2

Вот возможная рекурсия, которая рассматривает только квадратные сетки.

Существует два вида монотонных путей в сетке n × n , которые не пересекают диагональ: те, которые касаются диагонали в некоторой промежуточной точке (i, i) с 0 , а те, которые этого не делают.

• Путь по сетке n × n , который первым касается диагонали в (i, i) , можно разделить на две части: один путь по i × i сетка, которая не касается диагонали, и другая по сетке (ni) × (ni) , и они могут касаться диагонали. Это говорит о том, что вы можете сосчитать тех, у кого есть рекурсия, которая учитывает все возможные значения i.

• Путь, который не касается диагонали, начинается с «вправо» и заканчивается «вверх». Между этими двумя ходами лежит монотонный путь по сетке (n-1) × (n-1) , которая не пересекает диагональ, но может касаться ее.

Здесь мы вычисляем n ^th Каталонское число . Для этого есть формула, если вы хотите проверить свои рекурсивные вычисления.

Answer 3

Пусть номер пути, достигающего координаты (i,j), будет P(i,j).Поэтому (при условии, что нижний левый угол равен (0,0)):

P(i,j) = P(i-1,j) + P(i,j-1)

Вы можете дополнительно поставить условия координаты не ниже диагонали.То есть: i колеблется от 0..n, j колеблется от 0..n, но i<=j всегда.