Поможете новичку с проектом Эйлера?

Question

[Arbil]

Здрасте
Я начинающий программист
Я качестве прокачки "скилла" решаю задачки из "Проект Эйлера"
У меня возник Трудность с заданием № 15

Начиная в левом верхнем углу сетки 2×2 и имея возможность двигаться только вниз или вправо, существует ровно 6 маршрутов до правого нижнего угла сетки.

Сколько существует таких маршрутов в сетке 20×20?

До этого задания задания были сугубо связаны с числами и математическими вычислениями с которыми я ещё справлялся
Но тут я даже близко не знаю что делать
Направьте новичка на "путь правильного решения"
Может для компа какую-то разметку сделать или что-то вроде того

Понимаю вопрос ООООООЧЕНЬ расплывчатый, но прошу помочь

Comments

[Web Dentist]

https://tproger.ru/problems/grid-robot/

Answer 1

[longclaps]

Гугли "динамическое программирование".
Тут конкретно: берем матрицу 4x5 такого вида: (20x20 многовато для иллюстрации)

1 1 1 1 1
1 . . . .
1 . . . .
1 . . . .

Точки здесь - это те значения, которые будем вычислять.
Единички - это число способов попасть в соответствующую клетку из верхней левой (её координаты 0,0).
В клетку 1,1 можно попасть из 0,1 и 1,0 - запишем туда сумму значений из 0,1 и 1,0:

1 1 1 1 1
1 2 . . .
1 . . . .
1 . . . .

И так далее.