Грабим Дома на Собеседовании в Google 

незачем проверять четность, надо просто пересчитывать 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 ура!

A small hint: the buffer size is equal to the number of articles missed in the previous sentence. 😉

потому что резко, шустро, динамишно!

Дело тут в тех самых подзадачах. В них, та самая "динамика". Достаточно решить ее однажды и далее без повторного вычисления подставлять в общую формулу.

Потому что на каждом следующем шаге мы используем ранее полученные значения. Вот и динамическое.

зачем это обьяснять если это очевидно из смысла подхода. Решение находится не за один шаг как в простых алгоритмах, а это совокупность решений которые развиваются динамически один за одним и каждое последующее использует в основе предыдущее.

Суть динамического программирования в том, что ты описываешь логику для начальных базовых кейсов, а потом код начинает работать и при усложнении. Тут сеачала мы посчитали три базовых случая, а все остальные дома просто работали по уже имеющемуся алгоритму. Тебе не пришлось просчитывать все возможные комбинации и выбирать из них максимальное значение.

Имба

Я, видимо, не понимаю, что значит O(1). Это если это 1 ячейка памяти, то значит мы можем использовать только 1 переменную? А раз мы используем две, то это уже O(2)?

​@@6144100 О(1) значит, что вне зависимости от размера исхолного массива, вы будете использовать одинаковое количество памяти для хранения переменных при решении этой задачи.

@@6144100 не совсем, О(1) это не 1 ячейка памяти, а константая сложность, то есть если мы увеличим объем данных в 10 раз, мы все также будем использовать 2 переменные. На самом деле даже если использовать 10 переменных это все ещё будет О(1)

@@hegzom3747 спасибо

Если ответит или выйдет видео , можете пожалуйста написать

Практически любая задача на ДП канонически решается через рекурсию, а только потом оптимизируется, если есть необходимость. 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. Вот и все. Можно оставить в таком виде, а можно оптимизировать дальше, заменив передачу массива на индексы, переписать рекурсию в цикл (вариант из видео), уменьшить затраты памяти до константы (если есть возможность) и т.д.

PS в комментариях увидел и более лаконичный приём, вместо фиксированного хранилища для чётных и нечётных сумм, на каждом шаге они просто меняются местами, симулируя чёт и нечёт. Эффективности сильно не прибавляет, но выглядит явно красивее: def lave(a:list) -> int: even, odd = 0, 0 for cash in a: even, odd = odd, max(even + cash, odd) return odd

15 лет моего проф опыта голосуют однозначно за проекты.

делай проекты в которых нужны алгоритмы

Да? И чем же оно динамическое, раз Вам всё понятно? :)

@@MaxB4 пересмотрите несколько раз, если с первого раза не дошло

@@MaxB4 если и после этого не дойдет то найдите серию выпусков Андрея Грехова. там ДП для идиотов

@@sir890 Мне не нужна серия выпусков. 20+ лет в отрасли. Мне интересно, что в такого рода подачи материала понимают новички.

@@MaxB4 я в индустрии 14 лет и тоже знаю что такое ДП. по этому видео могу сказать что Саша дает хорошее базововое понятие подхода ДП для новичков.

В отпуске)

Проблема такого решения - использование в формуле решения для предыдущего дома т.к. если оно максимально, то оно обязательно включает в себя предыдущий дом, а это нарушает условие, что дома нельзя грабить подряд. А если в задаче есть отр. веса, то решение аналогично решению из видео, но первые 2 элемента dp нужно заполнить как max(0,a[0]), max(0, a[1]), чтобы не получить отрицательное значение в ответе. Ну или как вариант можно занулить или выбросить из списка вообще все неположительные значения.

Ещё и произносит _houses_ как [хаусэс]. Английского он в Лондоне, похоже, не слышал, и вообще МГИМО финишед.

Анализ готового решения увы обычно в разы проще его синтеза.

Дп - это индуктивный метод нахождения решения задачи при помощи решений задач меньшей размерности. Любой дп по сути - это рекуррентный алгоритм с меморизацией решений при помощи матрицы.

​@@dmitrysapelnikovаа, теперь понятно!

Это рекурсия, которая запоминает результат вычисления для текущего набора данных, и если аналогичный набор данных снова поступил на вход в процессе работы, то уже не вычисляет его, а сразу возвращает сохранённое значение. Эффективно, когда в теле рекурсии задача вызывает сама себя не один раз, как в тривиальной задаче про факториал, а несколько раз, например как при вычислении чисел Фибоначчи. Ну и конечно суть ДП не в рекурсии, любую рекурсию можно раскрыть в цикл, а в том, что мы запоминаем решения более простых задач и, как следствие, решаем их лишь один раз за проход.

Почему это проще?

@@FenBender01 в плане для понимания. Ты проверяешь на 2 дома назад и на 3(ведь проверят на 4 - это пропускать тот, что 2 назад). Он там усложнил(по моему)

Хвостовая рекурсия в общем случае будет иметь решение за o(n) по памяти, т.к. стек вызовов будет иметь глубину o(n). Но если транслятор/компилятор умеет ее оптимизировать, то да, он раскрутит ее в итеративный алгоритм со о1 по памяти.

Это уже другая задача, но ее решить несложно, достаточно хранить два массива индексов для прошлого и позапрошлого результата, а потом просто дополнять их в зависимости от принятого решения на каждом шаге.

Пройтись по полученому массиву справа налево Сравниваем 2 последних числа N-1 и N (N-1 >= N) Берём большее и записываем его индекс в сет. Если равные берём левое (N-1) Смещаемся влево. Если N было больше смещаемся на 2 (будем проверять N-3 и N-2), если было больше N-1, то смещаемся на 3 (будем проверять N-4 и N-3)

Тоже изучаю как выгоднее грабить дома, тут алгоритмы какие-то

потому что это название общей методики решения подобных задач, а не конкретный алгоритм. Аналог для понимания - сборка машины. Тебе насыпали все нужные детали и ты знаешь что и с чем правильно соединять. Но если ты начнешь это делать со случайного места, или просто будешь перебирать все варианты, то возможно у тебя что-то и выйдет, но ты потратишь немало времени на тупиковые ситуации, когда надо разобрать часть сделанного, чтобы туда впихнуть очередную нужную деталь. Но если ты будешь делать как положено: соберешь отдельно двигатель, отдельно кузов и т.д., то соединить уже готовые блоки в целое будет в разы проще и быстрее. Причем каждый более мелкий блок, например двигатель, тоже собирается из более простых блоков, которые надо предварительно правильно собрать и т.д. Причем собрав один раз колесо, тебе не надо ломать голову как собирать остальные три, для них у тебя будет готовый сохраненный алгоритм. Вот это и есть динамическое программирование. Надеюсь доступно объяснил.

@@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 Спасибо) Стало понятнее)

не хранить весь второй массив.

@@MaxB4 изменять входной массив?

@@reffatoriginal9054 нет. Просто хранить столько, сколько нужно для дальнейшей работы. Вам же для работы с 10м элементом первый уже не требуется?

да логика сильно запутанная, эффективность не менее квадрата, и ошибка уже в 3й строке функции, где обнуляется 2й элемент, если там скажем 1000, то вор не досчитается 1000 баксов.

@@SayXaNow спасибо, и вправду плохое решение

И самое главное что он работать не будет. Это - жадный алгоритм, он не применим для данного класса задач, о чем было сказано в видео. В таких задачах выбор самого большого текущего элемента не всегда приводит к оптимуму.

Просто исторический термин. Этот метод решения задач был разработан ещё в 40ых годах 20го века, до появления программирования в современном понимании.

@@dmitrysapelnikov тогда этот термин должен относиться к алгоритмам, а не к программированию. Нынче некоторые термины используют часто не к месту, а новичкам, посторонним и людям с критическим мышлением попробуй разберись.

Именно фронту это чаще и нужно. Бек отдал нужные данные и все. А сумму в конце листа или максимум из всех элементов под всеми элементами или вычислять координаты где нарисовать - делает именно фронт

Чтобы максимально эффективно разместить все элементы страницы, на площади окна произвольного размера.

Динамические алгоритмы делят задачу на кусочки и вычисляют их по очереди, шаг за шагом наращивая решения. Подход динамического программирования состоит в том, чтобы решить каждую подзадачу только один раз, сократив тем самым количество вычислений. Это особенно полезно в случаях, когда число повторяющихся подзадач экспоненциально велико.

@@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, имелось ввиду "алгоритмы динамического программирования", есть примеры таких алгоритмов.

Ну так и модифицируйте решение, чтобы оно возвращало порядок домов ) это несложно сделать.

Полностью согласен. Задача тупее некуда, не имеет реального смысла в прикладном программировании.

Задачи в школах, обычно, ставятся для развития навыка их решать. При успешном обучении с практикой вы сами должны справиться.

Ну до такого уровня как эта задача ещё нужны как показатель квалификации на уровнях middle+. Более сложные задачи - это уже спорт, крайне редко применимый в реальной работе.

@@dmitrysapelnikov а потом приходит ПМ и говорит "Мы тут хотим вот такую карусельку, тут чтоб вертикально скроллилась с пагинацией, а тут еще чтоб горизонтально, и еще свистоперделок хотим, анимаций и тп, тут нам видосики крути, а тут лотти анимашки и мы это хотим уже вчера" А ты только алгосы учил)) Ну это конечно сильно зависит от направления. Мож беку и надо.

А что тебе мешает с теми же затратами памяти O(N) вести дополнительно список номеров домов? Очевидно, что если текущий дом выгодно грабить, то просто добавляем этот номер в список.

так за это только похвалят. а прицепить к алгоритму еще и маршрут - это пара строчек.

Посмотри задачи на сайте Project Euler после номера 100 - эта задача по сравнению со многими задачами на том сайте просто лёгкая разминка.

Ну не скилбокс рекламить же

ну так канал русскоязычный, значит целевая аудитория - жители раши ;)

Ну может хорошие друзья попросили с яндекса). Да и деньги любые лишними не будут.

В Гугле не самые первоклассные программисты работают. Там в основном говнокодеры, проекты их посмотрите в исходниках, сплошной говнокод.