UniLecs #144. Super Mario
UniLecs
Задача: Вспоминаем легендарную игру Супер Марио. Надеюсь, все помнят правила: чтобы спасти принцессу, Супер Марио нужно преодолеть N ступенек. Также известно, что Марио прыжком может преодолеть не более K ступенек.
На его пути могут встретиться злобные черепахи, поэтому необходимо выяснить, сколько всего различных способов есть у Марио, чтобы добраться до принцессы.
Входные данные: N, K - натуральные числа от 1 до 100, где K <= N.
Вывод: кол-во всевозможных способов добраться до принцессы.
Пример:
1. N = 10; K = 1
Answer = 1
2. N = 4; K = 3
Answer = 7;
1 + 1 + 1 + 1; 1 + 1 + 2; 1 + 2 + 1;
2 + 1 + 1; 2 + 2;
1 + 3; 3 + 1
Идея: вспоминаем динамическое программирование: находим частный случай и от него отталкиваемся к общему решению.
Разберем алгоритм задачи на примере: N = 4; K = 3;
Обозначим за marioSteps[i] - кол-во способов дойти до iй ступеньки.
- Частный случай для N = 0. Если маршрут N = 0, то получаем, что марио "автоматически добрался до принцессы" и поэтому ответ = 1.
- Частный случай для N = 1. Если маршрут N = 1, то т.к. как марио может прыгать хотя бы на 1 ступеньку вперед (K > 0), то получаем также ответ = 1.
- Находим общее решение на разборе пример K = 3; N = 4:
marioSteps[2] = marioSteps[0] + marioSteps[1]
marioSteps[3] = marioSteps[0] + marioSteps[1] + marioSteps[2]
Т.к. как K = 3, то на 2ю и 3ю ступень мы можем попасть как с самого начала. Поэтому мы просто складываем кол-во способов попасть в 0ю ступень, 1ю и 2ю ступень соот-но.
marioSteps[4] = marioSteps[1] + marioSteps[2] + marioSteps[3]
На 4ю ступень из начала мы уже не можем, поэтому складываем способы попасть на 1ю, 2ю и 3ю ступень.
Аналогично делаем для 5, 6, 7й ступени:
marioSteps[5] = marioSteps[2] + marioSteps[3] + marioSteps[4]
marioSteps[6] = marioSteps[3] + marioSteps[4] + marioSteps[5]
marioSteps[7] = marioSteps[4] + marioSteps[5] + marioSteps[6]
Т.е. получили, что марио может попасть на N-ю ступеньку с предыдущих K. Давайте запрогаем то, что мы получили. Так как кол-во способов может быть большим, воспользуемся длинной арифметикой.
Реализация:
https://gist.github.com/unilecs/a2d9253ee8dc4cd5796df9743066842e