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

15 Мар 2020 в 19:45
163 +1
0
Ответы
1

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

Пусть 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 в правую верхнюю.

18 Апр 2024 в 16:12
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки в течение 1 года
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Поможем написать учебную работу
Прямой эфир