Один мой знакомый занимается составлением олимпиадных задач, которые впоследствии иногда дают на собеседованиях. Возникли затруднения с решением данной задачи:
В нашем зоопарке появился заяц. Его поместили в клетку, и чтобы ему не было скучно, директор зоопарка распорядился поставить в его клетке лесенку. Теперь наш зайчик может прыгать по лесенке вверх, перепрыгивая через ступеньки. Лестница имеет определенное количество ступенек N. Заяц может одним прыжком преодолеть не более К ступенек. Для разнообразия зайчик пытается каждый раз найти новый путь к вершине лестницы. Директору любопытно, сколько различных способов есть у зайца добраться до вершины лестницы при заданных значениях K и N. Помогите директору написать программу, которая поможет вычислить это количество. Например, если K=3 и N=4, то существуют следующие маршруты: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1. Т.е. при данных значениях у зайца всего 7 различных маршрутов добраться до вершины лестницы.
Хотелось бы узнать, что предложите вы. Мне интересен сам алгоритм, код далеко не так важен, но в любом случае это будет только плюсом =)
Ответ
Простейшая динамика (в которой я очень слаб, к сожалению)
Заведем массив dp размерностью n+1 (каждый i-й элемент будет хранить количество если бы было i ступенек)
dp[0]=1 //ступенек нет
Остальные рассчитываются как сумма всех предыдущих на расстоянии не больших k
Ответ в dp[n].
upd тоже код с acmp.ru
a[0] = BigInteger.ONE;
int start;
for (int i=1; i<=n; i++)
{
start = Math.max(0, i-k);
a[i] = BigInteger.ZERO;
for (int j=start; j
Комментариев нет:
Отправить комментарий