Слайд 8
ПРИМЕР ДВУМЕРНОЙ ДИНАМИКИ
Дано прямоугольное поле размером n на m клеток. Можно
совершать шаги длиной в одну клетку вправо и вниз. Посчитать, сколькими способами можно попасть из левой верхней клетки (с координатами (1,1)) в правую нижнюю (с координатами (n, m)).
В некоторую клетку с координатами (i,j) можно прийти только сверху или слева, т.е. из клеток с координатами (i-1, j) и (i, j-1).
Таким образом, для клетки (i, j) число маршрутов
A[i,j] = A[i-1,j] + A[i,j-1], т.е. задача сводится к двум подзадачам.
Необходимо последовательно пройти по строкам (или столбцам), находя число маршрутов для текущей клетки по формуле.
Тривиальный случай: A[1,1] = 1
Ответ находится в элементе A[n,m]