Question

ДАМ 50 БАЛЛОВ!!!!
В нижнем левом углу сетки 4×4 сидит мышь, а в правом верхнем углу лежит сыр. Мышь умеет перемещаться по сторонам клеток только вверх и вправо. Сколько различных путей может выбрать мышь, чтобы добраться до сыра?​

Answer 1

Ответ:

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

Сетка 4x4 имеет 4 строки и 4 столбца. Мышь начинает в левом нижнем углу и должна дойти до правого верхнего угла. Поскольку мышь может двигаться только вверх и вправо, она должна сделать 3 шага вверх и 3 шага вправо, чтобы достичь сыра.

Таким образом, задача сводится к нахождению количества уникальных перестановок 3 шагов вверх и 3 шагов вправо. Это можно вычислить, используя биномиальный коэффицие

Итак, у мыши есть 20 различных путей, чтобы добраться до сыра в данной сетке 4x4.