Условие:
Найдите количество таких путей из
Решение:
Шаг 1. Переход от геометрии к разности координат.
Рассмотрим точку пути (x,y) и введём разность d = x – y. Начальное состояние: d = 0, конечное (при x = n, y = n) также d = 0.
Каждый шаг меняется следующим образом:
• При шаге (1,0) x увеличивается на 1, значит d увеличивается на
1.
• При шаге (0,1) y увеличивается на 1, значит d уменьшается на
1.
При условии |x – y| ≤ 1 имеем |d| ≤ 1. Таким образом d всегда должно принадлежать множеству {–1, 0, 1}.
Шаг 2. Определение возможных переходов между состояниями.
Рассмотрим, каки...
Внутри — полный разбор, аргументация, алгоритм решения, частые ошибки и как отвечать на каверзные вопросы препода, если спросит
Попробуй решить по шагам
Попробуй один шаг и продолжи в режиме обучения или посмотри готовое решение
Что нужно знать по теме:
Что нужно знать по теме
Алгоритм решения
Топ 3 ошибок
Что спросит препод
Похожие задачи