Сообщение от Nerd96
Поссоны!
Задача 2. (30 баллов)
Фишка.
Фишка может двигаться только вперед по полю длины N.
Длина хода фишки не более K.
Найти число различных путей, по которым фишка может пройти поле от начала до конца.
Пример. N=3, K=2
Возможные пути:
1,1,1
1,2
2,1
Ответ: 3.
Не справился с этой на олимпиаде.
Пример загнал меня в глубокое непонимание.
Присутствовал инструктор, спросил у него - он ничего полезного не ответил.
|
Я так понял здесь следующее:
И да, количество способов продвижения фишки n+1 будет равно сумме предыдущих k способов.