Очень интересно. Только слово «пазл» несколько раздражает, в русском языке у него более узкое значение, мне кажется, что логичнее использовать слово «головоломка».
В 6-8 классах? Какой в этом смысл? Тем более, что поставленная цель — олимпиадное программирование. Достаточно объяснить использование конструкций вроде vector<int> и то делать это лучше после нескольких лет обучения.
Во-первых, чтобы написать программу, использующую мемоизацию, все равно необходимо вывести рекуррентное соотношение для исходной задачи. То есть основная идея останется той же, что и в ДП, но будет по-другому реализована.
Во-вторых, при использовании мемоизации может получиться очень большая глубина вызовов.
Не могу придумать, как реализовать динамическое программирование по профилю с помощью мемоизации.
Да, в первую очередь это методичка для ВУЗа. В полном виде, скорее всего, выставлено не будет. Предварительно я планировал выставить несколько наиболее интересных/сложных, на мой взгляд, параграфов в виде топиков и, возможно, в pdf.
Есть, например, Окулов «Программирование в алгоритмах», Меньшиков «Олимпиадные задачи по программированию». Большая часть тех книг по спортивному программированию, которые я читал, ориентирована в первую очередь на школьников.
Также отдельные разделы есть в классических книгах, посвященным алгоритмам.
Спасибо за подробный совет. Почему я включаю тривиальные задачи? Чтобы научиться решать сложные задачи, надо с чего-то начинать. На практике я для некоторых задач стараюсь дать несколько уровней сложности — чтобы, например, на первом уровне проходил алгоритм за O(n2), а на втором уже только за O(n * log(n)).
В планах задача о рюкзаке и динамика по профилю. Но в последней после статьи Василевского, мне кажется, сложно сказать что-то новое. Собираюсь включить ДП по профилю только из соображений системности изложения.
Про две кучи монет — спасибо. Как-то эта задача прошла мимо меня.
Как мне показалось, сейчас на олимпиадах серьезного уровня есть тенденция ухода от ДП. По крайней мере от динамического программирования в чистом виде. Так что можете радоваться :)
Во-вторых, при использовании мемоизации может получиться очень большая глубина вызовов.
Не могу придумать, как реализовать динамическое программирование по профилю с помощью мемоизации.
Есть, например, Окулов «Программирование в алгоритмах», Меньшиков «Олимпиадные задачи по программированию». Большая часть тех книг по спортивному программированию, которые я читал, ориентирована в первую очередь на школьников.
Также отдельные разделы есть в классических книгах, посвященным алгоритмам.
В планах задача о рюкзаке и динамика по профилю. Но в последней после статьи Василевского, мне кажется, сложно сказать что-то новое. Собираюсь включить ДП по профилю только из соображений системности изложения.
Про две кучи монет — спасибо. Как-то эта задача прошла мимо меня.