Какие ресурсы посоветуете по этим темам? В каком порядке (если это важно) их учить: дп потом разделяйка, разделяйка потом дп, или вообще без разницы? А еще какие интересные задачи (не совсем сложные) вы знаете на эти темы (если оставите ссылки - будет вообще супер). Хотелось бы сначала почитать/посмотреть что-то, а затем порешать ваши задачи. Спасибо.
Ну если ты говоришь про обычную разделяйку(не дп оптимизацию) то без разницы в каком порядке ты заботаешь это.
Как ботать разделяйку? Просто, можешь прочитать статью про сортировку слиянием(merge sort) и всё, абсолютно такая же идея обычно используется во всех задачах на разделяйку, только метод слияния разный. Можешь поискать гайды на codeforces, там же будут сборники задач на эту тему. Ещё можешь поискать прикольные применения разделяйки в этих же блогах
А вот с дп всё не так легко, вроде звучит просто “посчитай для меньших значений и с помощью них перейди в большие” или “Динамическое программирование — это когда у нас есть задача, которую непонятно как решать, и мы разбиваем ее на меньшие задачи, которые тоже непонятно как решать. (с) А.Кумок”. Вот и дп, но все равно спокойно решать задачи после того как ты узнал что такое дп не получится. Тут нужно просто решать большое количество задач набираясь опыта в:
- Какие переходы ты можешь делать.
- Какие могут быть состояния.
Могу порекомендовать atcoder educational dp conest, а для начала стоит прорешивать задачи на тему дп из архива acmp.ru(в порядке сложности (я так делал, прорешал первые 90 штук вроде)).Решая задачи ты узнаешь про разные виды ДП(digit dp, дп по поддеревьям и т.д.)
После того как получишь хорошую базу можешь начать изучать дп оптимизации(alien trick, d&c optimization, knuth optimization, convex hull trick, …).Но они почти не нужны, думаю сначала стоит добить Фиола-Оранжевого на кфе, путь к этому рейтингу будет в тыщу раз полезнее знания дп оптимизаций, да и с таким цветом довольно легко понять как работает большинство из этих оптимизаций.
Дальше идёт оффтоп.
Помню как задал вопрос про дп в чате и получил вот такой ответ от @Van 
:
5 лайков
Твой ответ на вопрос “как чалить дп” можно сжать в “Просто решаешь и все”))))))
Можете скинуть ссылку? Я нашел блоги, где обсуждаются d&c только для продвинутых
Там ниже есть ещё один абзац про дп оптимизации, плюс я скинул два ресурса с задачами и рассказал как я ботал дп на одном из них
3 лайка
Там был один пост с ссылкой на этот блог
3 лайка