Хабр Курсы для бэкендеров
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Поток Бэкенд доступен 24/7 благодаря поддержке друзей Хабра
Комментарии 13
У меня "проблема" с табличным DP. Даже перевести рекурсивное решение в табличное -- уже ступор. Смотрел видео, решал на бумажке: когда объяснённую задачу прорешиваешь -- вроде, понятно; но с нуля -- никак. Возможно, сказывается нехватка фундаментальных знаний и опыта.
Попробуй представить (или нарисовать) дерево решений и начать его проработку от листьев к корню. Мне тоже первое время рекурсивное решение с мемоизацией было приятнее, но потом я полюбил табличное даже больше - оно более компактное, не нужно писать лишних функций и структур данных.
P.S.: Но некоторые задачи не нужно переводить от рекурсивного в табличное - их лучше решать в рекурсивном, и наоборот. Итог - выбирай тот подход, который по задаче приятней
Надо формализовать решение. Когда вы выпишите математические функции, это все можно перевести в код не приходя в сознание. Потренеруйтесь это делать на куче задачек и потом станет легко.
В DP вам всегда надо обозначить функцию. Словами, формально определить ее. Вроде F(параметры) - это какое-то что-то при условии параметров.
Например: F(x,y) - максимальная сумма ячеек в пути в матрице с ходами влево-вниз, заканчивающихся в клетке x,y. F(n) - n-ое число фибоначчи. F(v, f) - минимальное количество вышек, расставленных в поддереве вершины v, так что все вершины в поддереве покрыты вышкой, кроме корня, а корень поддерева обязательно покрыт, если f=true. F(n,k) - количество способов разбить n на убывающие слагаемые такие, что первое не больше k.
Эти функции считают что-то: максимум, количество или какой-то оптимум среди каких-то объектов на множестве заданном параметрами.
Потом вам надо выписать рекуррентное соотношение: как функция F считается. В этом соотношении она будет считаться через саму себя. Для этого помогает как-то сгрупировать все объекты, с которыми функция работает. Вот эти параметры они задают какое-то множество чего-то. Путей в матрице, способов покрасить дерево, разбиений числа на слагаемые. Надо их как-то сгрупировать, чтобы получившееся подмножество описывалось такими же параметрами. В пути можно зафиксировать предпоследнюю вершину, в раскраске поддерева зафиксировать цвет корня и т.д. В каждом отдельном подмножестве вы ищите ответ той же функцией и объединяете ответы через сумму, максимум или что-то такое, что у вас в определении функции идет.
Уже посмотрев на эту формулу вы можете понять, в какую сторону идет зависимость, как параметры изменяются.
Потом вам надо обозначить базу. F от каких-то фиксированных параметров должна быть зафиксирована. Например, лучший путь из левого верхнего угла (0,0) в (0,0) единственен и вы все про него знаете. F(0,0) тут не надо считать. В поддереве из одного листа тоже все считается руками. В разбиении числа 1 на слагаемые есть только один вариант. И т.д.
Потом вам надо обозначить, где ответ - F от каких параметров решит вашу исходную задачу.
Потом уже можно реализовать рекурсивную функцию, просто переведя математическую формулу на язык програмимрования. А можно сделать таблично. Заведите таблицу F с теми же индексами, какие у вас параметры в функции. Посмотрев на формулу, разберитесь в каком порядке надо пустить циклы, чтобы все нужные для вычисления значения были подсчитаны перед использованием. Ну тупо, вот у вас F(x,...) зависит от F(x-1,...), значит x должен увеличиваться. С порядком циклов чуть-чуть сложне, тут может помочь нарисовать таблицу на бумаге, и из клеточки провести стрелочки в те, от которых клетка зависит, и подумать, в каком порядке обойти таблицу, чтобы вы никогда не шли по стрелочке, а только против них.
Ну и в цикле раелизуйте математическую формулу, только вместо вызовов рекурсивных функций берите значения из массива. Или можно вообще просто в цикле вызвать вашу изначально рекурсивную функцию, только вместо рекурсивных вызовов обращайтесь внутри к таблице.
Потом можно научиться писать более простой код за счет размазывания вычислений. Иногда проще не считать конкретную ячейку через предыдущие, а наоборот, смотреть, для каких ячеек текущая будет использоваться. И, если у вас там сумма в формуле, просто прибавлять текущее значения в следующие ячейки.
Потом можно научиться замечать, что в таблице всегда используются, допустим, 2 последние строки. И тогда не надо ее всю хранить. Или, как в числах фибоначчи, только 2 последних числа, вот их и храним.
"Если алгоритм корректен, не важно, какие там тест-кейсы и сколько их - задача пройдет"
Сортировка пузырьком вполне корректный алгоритм, но пройдет ли он все тест кейсы?
Здравствуйте, прочитал вашу статью она очень интересная и полезная. Я бы хотел у вас спросить совета: сам лично изучаю алгоритмы и язык программирования (С++ и питон). По С++ смотрю гайды и объяснения по поводу различного уровня задач на литкоде (изи/медиум), читаю метанит и learncpp. Но пока у меня проблемы до DP, я не дошёл и пока не умею пользоваться, подскажите пожалуйста как научиться хорошо решать на собеседованиях задачи чтобы их успешно проходить? Готовлюсь к весне чтобы попробовать попасть на Летнюю стажировку в Яндексе/Сбере, уделяю 1 час изучению и написанию кода(если бы не советовал учёба в вузе то уделял бы больше), и пишу мини пет проекты(клиентский HTTP/TCP сервер на С++ и на питоне свой RNA folding). Может быть вы знаете что мне не хватает или в какую тему глубже капнуть?
Попробуйте начать с теории и пару глав из CLRS пройти + упражнения на бумаге поделать, а уже потом переходить к LC
Спасибо за ответ, просто я планирую подготовиться и попасть на оплачиваемую стажировку в какой-нибудь бигтех с последующим трудоустройством (весной и летом у Яндекса, Сбера и Тинькоффа много открывается направлений), но пока подготовка страдает мало знаю легаси, STL и как вы писали в своей статьей DP. Могу пока работать с map, sort, arrays, set, vector, графы и деревья изучаю но пока есть пробелы
В каком направлении разработки действительно стоит уделять столько времени алгоритмике? Имхо это не совсем целесообразно когда речь идет о прикладной веб разработке, но в то же время я признаю что алгоритмические задачи отлично структурируют мышление в решении любых проблем программирования
Я на основной работе как раз и занимаюсь прикладной веб-разработкой )
в то же время я признаю что алгоритмические задачи отлично структурируют мышление в решении любых проблем программирования
Вот именно) Так что, в любом направлении стоит уделять много внимания алгоритмам
В бигтехе это постоянно вылезает. Особенно на бакенде и в клиентских (десктопных и мобильных) приложениях. На фронте в веб-разработке этого сильно меньше, но иногда тоже вылезает, если у вас что-то посложнее тривиальной формочки, а в бигтехе это часто. У меня пара статей с примерами есть тут на хабре: Алгоритмы нужны программистам.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Мой опыт решения 50 задач по динамическому программированию из LeetCode-плана за 24 дня