Сколькими способами муха может добраться из левой нижней клетки квадрата 7*7 в правую верхнюю? (За один ход муха может сместиться на одну клетку вправо или на одну клетку вверх.)

Предыдущий
вопрос Следующий
вопрос

Для того чтобы решить эту задачу, можно воспользоваться методом динамического программирования.

Пусть dp[i][j] - количество способов добраться из клетки (i, j) до правой верхней клетки. Так как муха за один ход может двигаться только вправо или вверх, то для клетки (i, j) количество способов равно сумме количества способов из клетки (i+1, j) и (i, j+1).

Исходя из этого, заполним массив dp следующим образом:
dp[7][7] = 1
for i = 6 to 0:
for j = 6 to 0:
dp[i][j] = dp[i+1][j] + dp[i][j+1]

Таким образом, dp[0][0] содержит количество способов добраться из левой нижней клетки квадрата 7*7 в правую верхнюю.