Грабим Дома на Собеседовании в Google
ฝัง
- เผยแพร่เมื่อ 12 มิ.ย. 2024
- Углубите знания во Фронтенд-разработке на курсе от Яндекс Практикума: ya.cc/t/11pC4NxQ4zgKAd
Erid: 2Vtzqws5UFs
Разбираем задачу из собеседований, в которой необходимо ограбить дома максимально эффективно, при этом не вызвав сигнализацию.
Задача решается с помощью Динамического Программирования. Это метод решения задач, в котором исходную трудную задачу мы разбиваем на маленькие подзадачи. Решаем в начале их, а потом собираем ответ на всю исходную задачу.
Задача на Leetcode: leetcode.com/problems/house-r...
00:00 Вступление
00:37 Условие
01:55 Первые идеи
03:02 Яндекс Практикум
04:34 Динамическое Программирование
10:01 Код Решения
Мой Телеграм канал: t.me/saschalukin
Решение за O(1) по памяти. Не нужен массив dp размером N. Нам ведь нужно хранить лишь предыдущих 2 суммы, все остальные бы больше никогда не будем использовать. Достаточно завести 2 переменные, скажем, "a" и "b". Теперь нам нужна гарантия, что мы учитываем сумму домов, стоящих хотя бы через 1 дом (по условию). По аналогии с видосом, будем брать максимум среди предыдущего максимума ([i - 1]) и того, что раньше ([i - 2] + текущий дом). Как мы будем понимать, когда учитывать переменную "a", а когда переменную "b"? Всё просто! Раз мы берем два соседних предыдущих максимума (i-1 отличается от i-2 на единицу), можем учитывать "a", когда встречаем чётный дом, и "b" - когда нечётный. В таком случае мы смотрим на четность дома, и в зависимости от неё, учитываем максимум либо в a = max(b, a + house[i]), или в b = (a, b + house[i]). Т.е. в случае с "a", мы будем смотреть, нам взять предыдущий максимум, или же пред-предыдущий(i-2) + текущий. В конце достаточно вернуть максимум из двух получившихся сумм (max(a, b)).
Вот для примера код на C++ (в стиле литкода):
int rob(vector& nums) {
int a = 0, b = 0, n = nums.size();
for(int i = 0; i < n; ++i)
(i&1) ? a = max(b, a + nums[i]) : b = max(a, b + nums[i]); // (i&1) проверяет четность, т.е. = 1(True) если число нечетное, иначе, False.
return max(a, b);
}
незачем проверять четность, надо просто пересчитывать a и b на каждой итерации:
const old_b = b;
b = Math.max(a + houses[i], b);
a = old_b;
а в конце return b;
в питоне можно было бы записать одной строчкой:
a, b = b , max(a + houses[i], b)
@@ventice11o факт
@@ventice11o в js/ts тоже можно одной строчкой :)
[preLast, last] = [last, Math.max(last, preLast + data[i])];
@@St1ggy ура!
Since you're not using entire array and only dp[i-1] and dp[i-2], you just need to keep small circular buffer.
A small hint: the buffer size is equal to the number of articles missed in the previous sentence. 😉
саша ты настоящая находка по разбору алгоритмов на ютубе. ещё не посмотрел ролик, но знаю, что он будет очень полезным
Большое спасибо за видео! Классно объясняешь
Спасибо большое. Очень интересно!
Вот теперь мне стало понятно. Супер!
Рассказано весьма подробно, но осталось не понятным почему это называется "динамическим" программированием?
потому что резко, шустро, динамишно!
Дело тут в тех самых подзадачах. В них, та самая "динамика". Достаточно решить ее однажды и далее без повторного вычисления подставлять в общую формулу.
Потому что на каждом следующем шаге мы используем ранее полученные значения. Вот и динамическое.
зачем это обьяснять если это очевидно из смысла подхода. Решение находится не за один шаг как в простых алгоритмах, а это совокупность решений которые развиваются динамически один за одним и каждое последующее использует в основе предыдущее.
Суть динамического программирования в том, что ты описываешь логику для начальных базовых кейсов, а потом код начинает работать и при усложнении. Тут сеачала мы посчитали три базовых случая, а все остальные дома просто работали по уже имеющемуся алгоритму. Тебе не пришлось просчитывать все возможные комбинации и выбирать из них максимальное значение.
Как же это гениально, спасибо, я все понял
Если так подумать, то мы используем только последние 2 ячейки массива dp, так что, чтобы получить O(1) памяти достаточно создать массив dp длиной в 2 ячейки и при прохождении по hоuses перезаписывать dp[1] в dp[0], а затем в dp[1] записывать новую максимальную сумму.
Это шикарно
Саня, лучший, спасибо тебе! Можно потратить день разбираясь с dp, а можно просто посмотреть Санино видео).
Кстати, задачу с роботом (которую ты разбирал несколько лет назад методом рекурсии), я думаю, тоже можно решить через dp, надо попробовать.
Класс, как всегда очень подробно и понятно, но задача, как ты и сказал, очень простая, разбери ту, что тебе давали решить. Кстати, вот пришла идея, что если рассматривать дома не в линейном массиве, а в двумерном, и тоже нельзя обкрадывать соседние дома, подход будет похожий, но механизм поиска сложнее.
Что думаешь о контестах в Codeforces, было бы интересно как ты решаешь какой-то контест хоть 3го дивизиона
Интересная задача !!!
Интересное решение!
возможно более доходчивый при изучении динпрога(если не вкуривать беллмановскую монографию) в данном случае хранить в массиве dp не итог а сумму достижимую когда бы "снимаем уражай" в текущей ячейке - тогда итерация dp[i]=house[i]+max(dp[i-2],dp[i-3]) - а ответ всегда есть мах(dp[i],dp[i-1) - imho такое заполнение больше соотвествует духу хранения рекурентностей
оу май какая задача на 0:11 под номером 174))). Это называется ♂right♂ задача, при решении которой сразу же берут на должность Java разраба
Спасибо большое за такой классный контент. ❤ Очень понятно и грамотно всё объясняешь, что даже вопросов не остаётся. Респект ✊
Наконец-то dyversity inclusif задачи от гугл
Отличный разбор. Все ясно и понятно.
О(1) от памяти это если хранить только dp[i-1], dp[i-2] в двух переменных ?
Саша, скажи пожалуйста на твой взгляд, какие онлайн курсы по программированию или школы по программированию достойны внимания.
Если ответит или выйдет видео , можете пожалуйста написать
👍
я так понимаю чтобы не тратить память, то нужно в исходный массив записывать посчитанные значения, которые в видео ты пишешь в отдельный массив dp т.к. мы повторно по исходному массиву не ходим
Типикал питон юзер сходу напишет нечто вроде этого, а потом уже будет думать над оптимизацией:
def lave(a:list) -> int:
return max(a[0] + lave(a[2:]), a[1] + lave(a[3:])) if len(a) > 1 else a[0] if a else 0
Взятие среза это чудовищно долго и почти куб по памяти в рекурсии, поэтому можно через индексы, стартуя с нулевого:
def lave(a:list, i:int = 0) -> int:
return max(a[i] + lave(a, i + 2), a[i + 1] + lave(a, i + 3)) if i < len(a) - 1 else a[i] if i < len(a) else 0
Это уже квадрат по памяти, но оба примера выше явные квадраты еще и по эффективности, т.к. всегда проверяют "хвост". Но заметив, что в рекурсии в max первый аргумент всегда чётные дома, а второй - всегда нечетные, и интересует только текущий максимальный результат, то можно его записывать в две дополнительные переменные (условно «чётная сумма» и «нечётная сумма»).
Логика такая: если текущий дом чётный и его сумма с накопленной чётной суммой больше, чем накопленная нечётная сумма, то записываем в чётную сумму «текущий дом + чётная сумма». В противном случае переписываем туда нечётную сумму, т.к. это лучший результат до этого момента. Аналогичным образом поступаем и с нечётным текущим домом.
Суммы реализованы через двухэлементный массив для прямой записи на основании четности индекса:
def lave(a:list) -> int:
sum = [0, 0]
for i, cash in enumerate(a):
sum[i % 2] = max(sum[0], sum[1] + cash) if i % 2 else max(sum[0] + cash, sum[1])
return max(sum)
PS в комментариях увидел и более лаконичный приём, вместо фиксированного хранилища для чётных и нечётных сумм, на каждом шаге они просто меняются местами, симулируя чёт и нечёт. Эффективности сильно не прибавляет, но выглядит явно красивее:
def lave(a:list) -> int:
even, odd = 0, 0
for cash in a:
even, odd = odd, max(even + cash, odd)
return odd
Интересно, сочетается ли это с рекурсией и есть ли смысл в рекурсии или выгоднее просто перезаписывать последние два значения. Есть ли задачи на динамическое программирование в которых рекурсия выгоднее буфера?
Практически любая задача на ДП канонически решается через рекурсию, а только потом оптимизируется, если есть необходимость.
1. Составляется общая рекурсия:
def lave(a:list) -> int:
return max(a[0] + lave(a[2:]), a[1] + lave(a[3:])) if len(a) > 2 else max(a, default=0)
Задача решена, но в таком виде не годится, т.к. количество рекурсивных вызовов растет экспоненциально.
2. Применяем меморизацию, это превратит к-во вызовов из экспоненты в линию:
d = {}
def lave(a:list) -> int:
if len(a) in d:
return d[len(a)]
else:
d[len(a)] = max(a[0] + lave(a[2:]), a[1] + lave(a[3:])) if len(a) > 2 else max(a, default=0)
return d[len(a)]
3. Вот и все. Можно оставить в таком виде, а можно оптимизировать дальше, заменив передачу массива на индексы, переписать рекурсию в цикл (вариант из видео), уменьшить затраты памяти до константы (если есть возможность) и т.д.
Есть вариант задачи когда дома стоят по кругу (то есть нельзя, например, грабить первый и последний дома). Рекомендую😉
С точки зрения JS не советую этот алгоритм так писать. У вас получается массив который имеет первые 1 и 2 элемента и остальные элементы empty, то есть создаете массив с дырками что применяется самые сложные оптимизации v8 и работать будет медленно.
Лучше хотя бы через .fill() заполнить с нулями
Круто! А вообще алгоритмы это конечно хорошо, но для трудоустройства маловато будет. На твой взгляд как будет лучше, начать с полного изучения алгоритмов и инструментария, или лучше сразу начать делать какие-то мини-проекты и вместе с Google изучать что попадётся по ходу дела? Я лично придерживаюсь второго сценария, но не уверен, в правильном ли направлении двигаюсь.
15 лет моего проф опыта голосуют однозначно за проекты.
делай проекты в которых нужны алгоритмы
Как всегда круто!
Privet! Otlichni kanal!
Sdelai razbor na zadachu pro permutations. Eto zadacha bila na sobesedovanii v Amazon.
House robber, сразу признал) Решал ее на литкоде, включая версию, когда дома замкнуты в круг))
Предполагаю, что для экономии памяти класть элементы, не в новый массив, а в исходный. Ну либо создать новый массив размером два
Одно из самых простых и понятных обьяснений ДП. Лайк
Да? И чем же оно динамическое, раз Вам всё понятно? :)
@@MaxB4 пересмотрите несколько раз, если с первого раза не дошло
@@MaxB4 если и после этого не дойдет то найдите серию выпусков Андрея Грехова. там ДП для идиотов
@@sir890 Мне не нужна серия выпусков. 20+ лет в отрасли. Мне интересно, что в такого рода подачи материала понимают новички.
@@MaxB4 я в индустрии 14 лет и тоже знаю что такое ДП. по этому видео могу сказать что Саша дает хорошее базововое понятие подхода ДП для новичков.
Объясните пожалуйста тему Greedy
Ты чего так начал часто выкладывать, все задачи в гугле сделал чтоли? Не сбавляй ход, жду еще новых разборов
В отпуске)
Не надо грабить, пожалуйста)
Можно перезаписывать массив домов)
Тяжело с динамикой у меня... Я думал, будет решение - dp[i] = сумма украденного после ограбления i-го дома. И равна max(dp[i-1], dp[i-2]) + houses[i]. И в конце берём макс от последних двух dp как ответ. Но если бы вдруг цифры могли быть отрицательными, моё решение перестало бы работать, а решение из видео и проще выглядит, и продолжило бы работать... Респект!)
Проблема такого решения - использование в формуле решения для предыдущего дома т.к. если оно максимально, то оно обязательно включает в себя предыдущий дом, а это нарушает условие, что дома нельзя грабить подряд. А если в задаче есть отр. веса, то решение аналогично решению из видео, но первые 2 элемента dp нужно заполнить как max(0,a[0]), max(0, a[1]), чтобы не получить отрицательное значение в ответе. Ну или как вариант можно занулить или выбросить из списка вообще все неположительные значения.
Спасибо за видео
Ммм, просто мозги радуются от твоих видео :D
Это просто огонь🎉
10:50 По-моему, ты где-то пропустил скобку: у тебя весь код в красных линиях)
прикольно... Человек-программист из google из Лондона, рекламирует яндекс-практикум. Ясно, понятно.
Ещё и произносит _houses_ как [хаусэс]. Английского он в Лондоне, похоже, не слышал, и вообще МГИМО финишед.
Круто! Не знаю Javascript и алгоритмы , но почти всё понятно в принципе.🤔
Анализ готового решения увы обычно в разы проще его синтеза.
конкретный пример понятен!
в общем случае, что такое ДП? если его нельзя объяснить, так может этот термин описывает то, чего нет?
Дп - это индуктивный метод нахождения решения задачи при помощи решений задач меньшей размерности. Любой дп по сути - это рекуррентный алгоритм с меморизацией решений при помощи матрицы.
@@dmitrysapelnikovаа, теперь понятно!
А с микрофоном (петличкой) было бы намного приятнее слушать ;-)
Решение за O(n) по времени и O(1) по памяти на Python:
class Solution:
def rob(self, nums: List[int]) -> int:
maxx=0
maxnum=0
for i in range(0,len(nums)):
if i>=2:
maxnum= max(nums[i-2],maxnum)
nums[i]+=maxnum
maxx = max(maxx,nums[i])
else:
maxx=max(maxx,nums[i])
return maxx
Имба
Я, видимо, не понимаю, что значит O(1). Это если это 1 ячейка памяти, то значит мы можем использовать только 1 переменную? А раз мы используем две, то это уже O(2)?
@@6144100 О(1) значит, что вне зависимости от размера исхолного массива, вы будете использовать одинаковое количество памяти для хранения переменных при решении этой задачи.
@@6144100 не совсем, О(1) это не 1 ячейка памяти, а константая сложность, то есть если мы увеличим объем данных в 10 раз, мы все также будем использовать 2 переменные. На самом деле даже если использовать 10 переменных это все ещё будет О(1)
@@hegzom3747 спасибо
Классно!
А что такое динамическое программирование? )
Это рекурсия, которая запоминает результат вычисления для текущего набора данных, и если аналогичный набор данных снова поступил на вход в процессе работы, то уже не вычисляет его, а сразу возвращает сохранённое значение. Эффективно, когда в теле рекурсии задача вызывает сама себя не один раз, как в тривиальной задаче про факториал, а несколько раз, например как при вычислении чисел Фибоначчи.
Ну и конечно суть ДП не в рекурсии, любую рекурсию можно раскрыть в цикл, а в том, что мы запоминаем решения более простых задач и, как следствие, решаем их лишь один раз за проход.
Саша, ты ювелир (от мира алгоритмов) 😂
В Англии есть компании , которые берут на работу удаленщиков вне Англии?
- "Значит так, на улице есть дома которые надо ограбить..."
- "О, это собеседование в Гугл?"
- "Гугл?"
Я бы решил чутка проще. DP[i] = max(DP[i-2], DP[i-3]) + houses[i]
После чего достаточно будет проверить какая из 2 последних значений DP больше
Почему это проще?
@@FenBender01 в плане для понимания. Ты проверяешь на 2 дома назад и на 3(ведь проверят на 4 - это пропускать тот, что 2 назад). Он там усложнил(по моему)
Решение за О(1) по памяти-это хвостовая рекурсия?
Хвостовая рекурсия в общем случае будет иметь решение за o(n) по памяти, т.к. стек вызовов будет иметь глубину o(n). Но если транслятор/компилятор умеет ее оптимизировать, то да, он раскрутит ее в итеративный алгоритм со о1 по памяти.
вооооу, 2 видео за неделю. что случилось?)
а что на счёт индексов "домов" в итоге? мне, как вору, хотелось бы ещё знать какие дома грабить, а не только максимальный кэш с данной "улицы" :)
по ходу выполнения алгоритма, отвечать на этот вопрос у нас не получится, т.к. мы не знаем сколько денег в следующих домах, такой вывод мы можем сделать на основе собранного массива dp.
Или нет?
Это уже другая задача, но ее решить несложно, достаточно хранить два массива индексов для прошлого и позапрошлого результата, а потом просто дополнять их в зависимости от принятого решения на каждом шаге.
Пройтись по полученому массиву справа налево
Сравниваем 2 последних числа N-1 и N (N-1 >= N)
Берём большее и записываем его индекс в сет. Если равные берём левое (N-1)
Смещаемся влево. Если N было больше смещаемся на 2 (будем проверять N-3 и N-2), если было больше N-1, то смещаемся на 3 (будем проверять N-4 и N-3)
Как раз второй день с переменным успехом пытаюсь врубиться в эту тему😅
Тоже изучаю как выгоднее грабить дома, тут алгоритмы какие-то
Так в чём динамичнось-то?
походу Google планирует новый сервис/приложение для грабителей в Сан-Франциско для максимализации прибыли
Тяжелые времена настали у программистов, решаем грабить дом или нет
Спасибо, полезно)
не пойму только почему это называется динамическое программированмие, а не просто алгоритм такой то)
потому что это название общей методики решения подобных задач, а не конкретный алгоритм. Аналог для понимания - сборка машины. Тебе насыпали все нужные детали и ты знаешь что и с чем правильно соединять. Но если ты начнешь это делать со случайного места, или просто будешь перебирать все варианты, то возможно у тебя что-то и выйдет, но ты потратишь немало времени на тупиковые ситуации, когда надо разобрать часть сделанного, чтобы туда впихнуть очередную нужную деталь. Но если ты будешь делать как положено: соберешь отдельно двигатель, отдельно кузов и т.д., то соединить уже готовые блоки в целое будет в разы проще и быстрее. Причем каждый более мелкий блок, например двигатель, тоже собирается из более простых блоков, которые надо предварительно правильно собрать и т.д. Причем собрав один раз колесо, тебе не надо ломать голову как собирать остальные три, для них у тебя будет готовый сохраненный алгоритм. Вот это и есть динамическое программирование. Надеюсь доступно объяснил.
@@SayXaNow Ну более менее понятно, спасибо! Только непонятно как определять, что в задаче нужно применять именно динамическое программирование, а не просто какой то алгоритм
Ну один из основных признаков: если явно прослеживается рекурсивный алгоритм. Суть динамического программирования - это если подзадача была вызвана с определенным набором данных, то этот результат кэшируется, и когда на вход подзадачи попадет точно такой же набор данных, то он уже будет не вычисляться, а сразу возьмётся из памяти. Таким образом эта подзадача будет вычислена только один раз. Что серьёзно сократит время, жертвуя памятью на сохранение результатов.
Рассмотрим, как решал задачу из видео я. Сходу приходит очень простое рекурсивное решение: берем первый дом и складываем его со всеми домами без первых двух, вызывая ту же саму функцию, но уже с сокращенным списком домов. Но мы можем начать и со второго дома, поэтому также находим сумму второго дома и результата вызова урезанного массива через один дом от него. С третьего дома начинать нет смысла, т.к. можно захватить в этом случае и первый дом, т.е. это наш первый вариант.
Таким образом нам всего на всего надо рекурсивно посчитать два варианта и вернуть максимальный. Записывается однострочником:
def lave(a:list) -> int:
return max(a[0] + lave(a[2:]), a[1] + lave(a[3:])) if len(a) > 2 else max(a, default=0)
Задача решена, но в чем проблема? Проблема в том, что на каждом шаге рекурсия вызывает себя дважды - в первом аргументе max и во втором, и количество вызовов удваивается с каждой глубиной, т.е. оно растет экспоненциально. Если поставить счетчик вызовов, то уже для N=50, количество вызовов приблизится к полутора миллионов, с большим N лучше и не пробовать, есть шансы что не дождешься результата никогда.
Какой выход? Применить ДП. Мы будем сохранять результат в словаре, где ключ - это длина массива, а значение - это посчитанный самый оптимальный ответ для данного размера массива. Таким образом получим набор уже готовых решённых подзадач, и если функция увидит, что в словаре уже есть такая длина, то сразу вернет значение, без рекурсивного вычисления, и для каждого размера отработает только один раз.
d = {}
def lave(a:list) -> int:
if len(a) in d:
return d[len(a)]
else:
d[len(a)] = max(a[0] + lave(a[2:]), a[1] + lave(a[3:])) if len(a) > 2 else max(a, default=0)
return d[len(a)]
Вот и все, теперь алгоритм работает за O(2N) - линейное время, но съедает O(N) дополнительной памяти на хранение промежуточных результатов. Как правило пример, подобный моему ходу решения и приводится как канон ДП. Главная суть ДП - избежать повторного вычисления уже посчитанных данных и заключается она не в самой рекурсии, а в том, что мы стали применять кэширование результата, получая список уже готовых решений для мелких подзадач. Признаки что можно применять ДП: задачу можно рекурсивно разбить на несколько более простых подзадач схожего типа и, как правило, в теле основной задачи есть несколько таких подзадач.
@@SayXaNow Спасибо) Стало понятнее)
Как сделать О(1) по памяти?
не хранить весь второй массив.
@@MaxB4 изменять входной массив?
@@reffatoriginal9054 нет. Просто хранить столько, сколько нужно для дальнейшей работы. Вам же для работы с 10м элементом первый уже не требуется?
Не понимаю нафиг кому нужны алгоритмы, но так уж и быть попробую написать решение, которое первое приходит в голову до просмотра ответа:
Дан массив из n чисел A, создадим еще один массив S той же длины.
Заполним его S[0] = A[0]; S[1] = Max(A[0], A[1]); S[i] = Max(S[i - 1], S[i-2] + A[i])
Выведем S[n-1]
PS. По сути можно вообще массивы не создавать, а в памяти держать 3 числа, считая всё прямо во время ввода, но это че-то совсем задротство)
PPS. Какие еще алгоритмы в собеседовании на фронтенд разработчика?🤣
А где доказательство, что это точно будет правильное решение? С точки зрения математики можно было бы сформулировать через индукцию, например. Было бы полезно.
Снимай как можно больше таких роликов! Это просто огонь!
динамическое программирование?? не метод математической индукции?
По-моему я уже видел этот ролик... перезалив?
написал такую программу на пайтон с другим решением. Но видимо мой вариант неэффективный
houses_ = [4, 11, 10, 2, 1, 8, 5]
def best(houses):
money = houses[0]
houses[0] = 0
houses[1] = 0
while len(houses) != houses.count(0):
maximum = max(houses)
max_index = houses.index(maximum)
houses[max_index] = 0
if max_index == len(houses) - 1:
houses[max_index - 1] = 0
elif max_index == 0:
houses[max_index + 1] = 0
else:
houses[max_index - 1] = 0
houses[max_index + 1] = 0
money += maximum
return money
print(best(houses_))
да логика сильно запутанная, эффективность не менее квадрата, и ошибка уже в 3й строке функции, где обнуляется 2й элемент, если там скажем 1000, то вор не досчитается 1000 баксов.
@@SayXaNow спасибо, и вправду плохое решение
И самое главное что он работать не будет. Это - жадный алгоритм, он не применим для данного класса задач, о чем было сказано в видео. В таких задачах выбор самого большого текущего элемента не всегда приводит к оптимуму.
Крутой🫡
По ходу Саша услышал комментаторов и стал выпускать видео чаще)) Я наконец разложил для себя по полочкам дин. программирование) Спасибо!
Будет круто увидеть еще видео про backtracking. Лайкайте этот комментарий, кому тоже интересно, чтобы Саша увидел и прислушался)
А почему это называется динамическое программирование?
Просто исторический термин. Этот метод решения задач был разработан ещё в 40ых годах 20го века, до появления программирования в современном понимании.
@@dmitrysapelnikov тогда этот термин должен относиться к алгоритмам, а не к программированию. Нынче некоторые термины используют часто не к месту, а новичкам, посторонним и людям с критическим мышлением попробуй разберись.
Осталось только узнать зачем это фронтендеру 😂
Именно фронту это чаще и нужно. Бек отдал нужные данные и все. А сумму в конце листа или максимум из всех элементов под всеми элементами или вычислять координаты где нарисовать - делает именно фронт
Чтобы максимально эффективно разместить все элементы страницы, на площади окна произвольного размера.
Всё ! Идём на "дело" 🤭
задачки, "как своровать лучше?", очень в стиле капитализма))00
Алгоритм понятен. Не понятно почему это называется динамическим программированием?
Динамические алгоритмы делят задачу на кусочки и вычисляют их по очереди, шаг за шагом наращивая решения.
Подход динамического программирования состоит в том, чтобы решить каждую подзадачу только один раз, сократив тем самым количество вычислений. Это особенно полезно в случаях, когда число повторяющихся подзадач экспоненциально велико.
@@telekanalDobro например, если у нас есть база данных, в которой много таблиц, у нас есть простые сущности - типы данных или модели по другому или еще по другому классы, и например каждый класс по своей структуре соответствует каждой из таблиц базы данных, если нам надо собрать сложный dto , который состоит из классов, которые являются моделями данных для таблиц в базе, и вот есть два варианта десериализации - первый это сложный запрос, который будет на выходе содержать все необходимые данные для сложного dto, и второй вариант , написать несколько маленьких запросов, результаты которых будут десериализованы в простые dto, а потом из этих простых dto собрать уже сложный dto, будет ли это динамическим программированием или нет? Формально, десериализацию сложного dto, мы делим на кусочки и по очереди их вычисляем.
В данном примере
dp [i] = max (houses [i] + dp [i-2], dp [i-1]),
динамическим является (houses [i] + dp [i-2]), так как в алгоритме dp [i-2] повторяется, являясь основой для последующих i в массиве.
В этом и заключается динамика расчета в примере.
А в вашем случае, пусть автор ролика попробует ответить, допустив, что ему такой вопрос задали бы на собеседовании в гугл.
@@telekanalDobro речь шла про программирование, а Вы говорите про алгоритмы. Это разные вещи.
@@MaxB4, имелось ввиду "алгоритмы динамического программирования", есть примеры таких алгоритмов.
Задача то бессмысленная, какая-то олимпиадная. Вот если сохранять номера домов, чтобы был понятен маршрут бандитов. И результатом функции, был бы порядок домов и сумма. То возможно такой алгоритм, мог бы быть полезным. Алгоритмы ради алгоритмов, программирование для собеседований.
Ну так и модифицируйте решение, чтобы оно возвращало порядок домов ) это несложно сделать.
Полностью согласен. Задача тупее некуда, не имеет реального смысла в прикладном программировании.
Задачи в школах, обычно, ставятся для развития навыка их решать. При успешном обучении с практикой вы сами должны справиться.
Похоже это уже устоявшаяся не правильная практика, на собеседование давать подобные алгоритмические задачи при том, что они не имеют обсолютно никакого отношению к работе кандидата. А решение подобных задач это отдельный скил, который часто присушь тем, кто занимался соревновательным программированием.
Саша возвращайся в Россию.
В гугл спрашивают как грабить дома? Понятно
Динамическое программирование это когда вы решаете задачу для n мерного массива , а n любое целое число. Задача тут не принципиальная.
чего js ого
Это какой то сюр. Кому в проде нужны эти алгоритмы? Гуглу и Яду?
Ну до такого уровня как эта задача ещё нужны как показатель квалификации на уровнях middle+. Более сложные задачи - это уже спорт, крайне редко применимый в реальной работе.
@@dmitrysapelnikov а потом приходит ПМ и говорит "Мы тут хотим вот такую карусельку, тут чтоб вертикально скроллилась с пагинацией, а тут еще чтоб горизонтально, и еще свистоперделок хотим, анимаций и тп, тут нам видосики крути, а тут лотти анимашки и мы это хотим уже вчера" А ты только алгосы учил)) Ну это конечно сильно зависит от направления. Мож беку и надо.
Бляха, 10 лет работаю программистом. Подобную херабору решал последний раз на 2 курсе, тобишь лет 12 назад. Какие сверх разумы ставят эти задачи программистам ? У кого такие задачи возникают в ежедневной деятельности?) Все что вы узнаете из таких задач про программиста что он надроченый олимпиадник и на практике далеко не факт что будет с него толк.
По факту проверка на то прорешал ли человек весь литкод)
Я обязательно выживу......
Задача, конечно, интнресная, но результат, который возвращает показанная реализация, не имеет практического смысла. Грабителям надо знать не просто максимальную сумму, которую можно украсть, им надо знать ещё и какие дома надо обносить.
А что тебе мешает с теми же затратами памяти O(N) вести дополнительно список номеров домов? Очевидно, что если текущий дом выгодно грабить, то просто добавляем этот номер в список.
Самый сложный ролик вышел 😅
Сформулировал задачу кривовато. Если её так выдать на собеседовании, часть собеседуемых посчитает, что нужно определить не только максимальную сумму, но и список домов из-за того, что это показано в начале подчеркиванием их и невнятно сформулированной задачей озвученной в это же время.
так за это только похвалят. а прицепить к алгоритму еще и маршрут - это пара строчек.
Ктооо придумывает эти задачи, ее так понять нельзя, а еще в коде написать.
Посмотри задачи на сайте Project Euler после номера 100 - эта задача по сравнению со многими задачами на том сайте просто лёгкая разминка.
Это безсмыслица разбирать конкретные алгоритмы. Человеку либо дано программирование сложных задач, либо нет. В гугле кстати работают далеко не самые первоклассные программисты. Если пошариться по исходникам различных гугловских проектов - говнокода, том числе не оптимизированного дохера и больше.
Мне очень странно видеть чувака, который работает в гугле, но при этом рекламит курсы яндекс практикума......
📌 И не врите самому себе про Рабочий День
👀 th-cam.com/video/926m0lGEHw4/w-d-xo.htmlsi=PHejZZ1pJ436F9Sr
Работает в Google в Lондоне и рекламирует курсы от яндекса)))) По-моему парнишка привирает)))
Ну не скилбокс рекламить же
ну так канал русскоязычный, значит целевая аудитория - жители раши ;)
Ну может хорошие друзья попросили с яндекса). Да и деньги любые лишними не будут.
В Гугле не самые первоклассные программисты работают. Там в основном говнокодеры, проекты их посмотрите в исходниках, сплошной говнокод.