Решение за 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 (i&1) ? a = max(b, a + nums[i]) : b = max(a, b + nums[i]); // (i&1) проверяет четность, т.е. = 1(True) если число нечетное, иначе, False. return max(a, b); }

@ventice11o

Ай бұрын

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

@progressiveaccount3270

Ай бұрын

@@ventice11o факт

@St1ggy

Ай бұрын

@@ventice11o в js/ts тоже можно одной строчкой :) [preLast, last] = [last, Math.max(last, preLast + data[i])];

@ventice11o

Ай бұрын

@@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.

@dmitrysapelnikov

Ай бұрын

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

Саня, лучший, спасибо тебе! Можно потратить день разбираясь с dp, а можно просто посмотреть Санино видео). Кстати, задачу с роботом (которую ты разбирал несколько лет назад методом рекурсии), я думаю, тоже можно решить через dp, надо попробовать.

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

Это шикарно

Если так подумать, то мы используем только последние 2 ячейки массива dp, так что, чтобы получить O(1) памяти достаточно создать массив dp длиной в 2 ячейки и при прохождении по hоuses перезаписывать dp[1] в dp[0], а затем в dp[1] записывать новую максимальную сумму.

Интересная задача !!!

возможно более доходчивый при изучении динпрога(если не вкуривать беллмановскую монографию) в данном случае хранить в массиве dp не итог а сумму достижимую когда бы "снимаем уражай" в текущей ячейке - тогда итерация dp[i]=house[i]+max(dp[i-2],dp[i-3]) - а ответ всегда есть мах(dp[i],dp[i-1) - imho такое заполнение больше соотвествует духу хранения рекурентностей

Интересное решение!

Решение за 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

@enhograzy443

Ай бұрын

Имба

@6144100

28 күн бұрын

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

@user-xz6fc4qs9o

28 күн бұрын

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

@hegzom3747

27 күн бұрын

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

@6144100

27 күн бұрын

@@hegzom3747 спасибо

Наконец-то dyversity inclusif задачи от гугл

Есть вариант задачи когда дома стоят по кругу (то есть нельзя, например, грабить первый и последний дома). Рекомендую😉

Рассказано весьма подробно, но осталось не понятным почему это называется "динамическим" программированием?

@1001bit

Ай бұрын

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

@yuriynicom

Ай бұрын

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

@panfilovandrey

29 күн бұрын

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

@sir890

29 күн бұрын

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

@alexeydorosh955

27 күн бұрын

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

👍

House robber, сразу признал) Решал ее на литкоде, включая версию, когда дома замкнуты в круг))

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

Что думаешь о контестах в Codeforces, было бы интересно как ты решаешь какой-то контест хоть 3го дивизиона

Одно из самых простых и понятных обьяснений ДП. Лайк

@MaxB4

Ай бұрын

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

@sir890

Ай бұрын

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

@sir890

Ай бұрын

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

@MaxB4

29 күн бұрын

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

@sir890

29 күн бұрын

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

С точки зрения JS не советую этот алгоритм так писать. У вас получается массив который имеет первые 1 и 2 элемента и остальные элементы empty, то есть создаете массив с дырками что применяется самые сложные оптимизации v8 и работать будет медленно. Лучше хотя бы через .fill() заполнить с нулями

Тяжело с динамикой у меня... Я думал, будет решение - dp[i] = сумма украденного после ограбления i-го дома. И равна max(dp[i-1], dp[i-2]) + houses[i]. И в конце берём макс от последних двух dp как ответ. Но если бы вдруг цифры могли быть отрицательными, моё решение перестало бы работать, а решение из видео и проще выглядит, и продолжило бы работать... Респект!)

@dmitrysapelnikov

Ай бұрын

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

Типикал питон юзер сходу напишет нечто вроде этого, а потом уже будет думать над оптимизацией: 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 Это уже квадрат по памяти, но оба примера выше явные квадраты еще и по эффективности, т.к. всегда проверяют "хвост". Но заметив, что в рекурсии в 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)

@SayXaNow

Ай бұрын

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

Можно перезаписывать массив домов)

оу май какая задача на 0:11 под номером 174))). Это называется ♂right♂ задача, при решении которой сразу же берут на должность Java разраба

Отличный разбор. Все ясно и понятно.

Спасибо большое за такой классный контент. ❤ Очень понятно и грамотно всё объясняешь, что даже вопросов не остаётся. Респект ✊

Ммм, просто мозги радуются от твоих видео :D

Privet! Otlichni kanal! Sdelai razbor na zadachu pro permutations. Eto zadacha bila na sobesedovanii v Amazon.

Круто! А вообще алгоритмы это конечно хорошо, но для трудоустройства маловато будет. На твой взгляд как будет лучше, начать с полного изучения алгоритмов и инструментария, или лучше сразу начать делать какие-то мини-проекты и вместе с Google изучать что попадётся по ходу дела? Я лично придерживаюсь второго сценария, но не уверен, в правильном ли направлении двигаюсь.

@dmitrysapelnikov

Ай бұрын

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

@xz8928

Ай бұрын

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

Интересно, сочетается ли это с рекурсией и есть ли смысл в рекурсии или выгоднее просто перезаписывать последние два значения. Есть ли задачи на динамическое программирование в которых рекурсия выгоднее буфера?

@SayXaNow

24 күн бұрын

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

Саша, скажи пожалуйста на твой взгляд, какие онлайн курсы по программированию или школы по программированию достойны внимания.

@user-qp3oe5fv4t

29 күн бұрын

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

Я бы решил чутка проще. DP[i] = max(DP[i-2], DP[i-3]) + houses[i] После чего достаточно будет проверить какая из 2 последних значений DP больше

@FenBender01

Ай бұрын

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

@user-mo8zi6uc4d

Ай бұрын

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

конкретный пример понятен! в общем случае, что такое ДП? если его нельзя объяснить, так может этот термин описывает то, чего нет?

@dmitrysapelnikov

Ай бұрын

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

@igorkolesnikov1596

Ай бұрын

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

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

О(1) от памяти это если хранить только dp[i-1], dp[i-2] в двух переменных ?

Спасибо за видео

Как всегда круто!

Объясните пожалуйста тему Greedy

10:50 По-моему, ты где-то пропустил скобку: у тебя весь код в красных линиях)

Не надо грабить, пожалуйста)

Круто! Не знаю Javascript и алгоритмы , но почти всё понятно в принципе.🤔

@dmitrysapelnikov

Ай бұрын

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

прикольно... Человек-программист из google из Лондона, рекламирует яндекс-практикум. Ясно, понятно.

@boderaner

Ай бұрын

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

Это просто огонь🎉

Ты чего так начал часто выкладывать, все задачи в гугле сделал чтоли? Не сбавляй ход, жду еще новых разборов

@sashalukin

Ай бұрын

В отпуске)

Классно! А что такое динамическое программирование? )

@SayXaNow

Ай бұрын

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

вооооу, 2 видео за неделю. что случилось?)

А с микрофоном (петличкой) было бы намного приятнее слушать ;-)

а что на счёт индексов "домов" в итоге? мне, как вору, хотелось бы ещё знать какие дома грабить, а не только максимальный кэш с данной "улицы" :) по ходу выполнения алгоритма, отвечать на этот вопрос у нас не получится, т.к. мы не знаем сколько денег в следующих домах, такой вывод мы можем сделать на основе собранного массива dp. Или нет?

@panfilovandrey

29 күн бұрын

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

@user-zl4uq4on1o

21 күн бұрын

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

написал такую программу на пайтон с другим решением. Но видимо мой вариант неэффективный 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_))

@SayXaNow

Ай бұрын

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

@lagomchannel5953

Ай бұрын

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

@dmitrysapelnikov

Ай бұрын

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

Саша, ты ювелир (от мира алгоритмов) 😂

- "Значит так, на улице есть дома которые надо ограбить..." - "О, это собеседование в Гугл?" - "Гугл?"

Спасибо, полезно) не пойму только почему это называется динамическое программированмие, а не просто алгоритм такой то)

@SayXaNow

Ай бұрын

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

@Mr.Bellamy

Ай бұрын

@@SayXaNow Ну более менее понятно, спасибо! Только непонятно как определять, что в задаче нужно применять именно динамическое программирование, а не просто какой то алгоритм

@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) дополнительной памяти на хранение промежуточных результатов. Как правило пример, подобный моему ходу решения и приводится как канон ДП. Главная суть ДП - избежать повторного вычисления уже посчитанных данных и заключается она не в самой рекурсии, а в том, что мы стали применять кэширование результата, получая список уже готовых решений для мелких подзадач. Признаки что можно применять ДП: задачу можно рекурсивно разбить на несколько более простых подзадач схожего типа и, как правило, в теле основной задачи есть несколько таких подзадач.

@Mr.Bellamy

Ай бұрын

@@SayXaNow Спасибо) Стало понятнее)

Решение за О(1) по памяти-это хвостовая рекурсия?

@dmitrysapelnikov

Ай бұрын

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

Как раз второй день с переменным успехом пытаюсь врубиться в эту тему😅

@FaxWeb7

Ай бұрын

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

В Англии есть компании , которые берут на работу удаленщиков вне Англии?

Крутой🫡

Тяжелые времена настали у программистов, решаем грабить дом или нет

Осталось только узнать зачем это фронтендеру 😂

@aliday9968

27 күн бұрын

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

@victorkochkarev2576

22 күн бұрын

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

Как сделать О(1) по памяти?

@MaxB4

Ай бұрын

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

@reffatoriginal9054

Ай бұрын

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

@MaxB4

29 күн бұрын

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

Так в чём динамичнось-то?

походу Google планирует новый сервис/приложение для грабителей в Сан-Франциско для максимализации прибыли

По-моему я уже видел этот ролик... перезалив?

Задача то бессмысленная, какая-то олимпиадная. Вот если сохранять номера домов, чтобы был понятен маршрут бандитов. И результатом функции, был бы порядок домов и сумма. То возможно такой алгоритм, мог бы быть полезным. Алгоритмы ради алгоритмов, программирование для собеседований.

@dmitrysapelnikov

Ай бұрын

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

@rtfdfhjrggth4220

Ай бұрын

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

@MaxB4

Ай бұрын

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

А где доказательство, что это точно будет правильное решение? С точки зрения математики можно было бы сформулировать через индукцию, например. Было бы полезно.

Алгоритм понятен. Не понятно почему это называется динамическим программированием?

@telekanalDobro

Ай бұрын

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

@bulatnikoffdmitrii4438

Ай бұрын

@@telekanalDobro например, если у нас есть база данных, в которой много таблиц, у нас есть простые сущности - типы данных или модели по другому или еще по другому классы, и например каждый класс по своей структуре соответствует каждой из таблиц базы данных, если нам надо собрать сложный dto , который состоит из классов, которые являются моделями данных для таблиц в базе, и вот есть два варианта десериализации - первый это сложный запрос, который будет на выходе содержать все необходимые данные для сложного dto, и второй вариант , написать несколько маленьких запросов, результаты которых будут десериализованы в простые dto, а потом из этих простых dto собрать уже сложный dto, будет ли это динамическим программированием или нет? Формально, десериализацию сложного dto, мы делим на кусочки и по очереди их вычисляем.

@telekanalDobro

Ай бұрын

В данном примере dp [i] = max (houses [i] + dp [i-2], dp [i-1]), динамическим является (houses [i] + dp [i-2]), так как в алгоритме dp [i-2] повторяется, являясь основой для последующих i в массиве. В этом и заключается динамика расчета в примере. А в вашем случае, пусть автор ролика попробует ответить, допустив, что ему такой вопрос задали бы на собеседовании в гугл.

@MaxB4

Ай бұрын

@@telekanalDobro речь шла про программирование, а Вы говорите про алгоритмы. Это разные вещи.

@telekanalDobro

Ай бұрын

​@@MaxB4, имелось ввиду "алгоритмы динамического программирования", есть примеры таких алгоритмов.

Снимай как можно больше таких роликов! Это просто огонь!

А почему это называется динамическое программирование?

@dmitrysapelnikov

Ай бұрын

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

@MaxB4

Ай бұрын

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

динамическое программирование?? не метод математической индукции?

задачки, "как своровать лучше?", очень в стиле капитализма))00

Всё ! Идём на "дело" 🤭

Саша возвращайся в Россию.

По ходу Саша услышал комментаторов и стал выпускать видео чаще)) Я наконец разложил для себя по полочкам дин. программирование) Спасибо! Будет круто увидеть еще видео про backtracking. Лайкайте этот комментарий, кому тоже интересно, чтобы Саша увидел и прислушался)

Динамическое программирование это когда вы решаете задачу для n мерного массива , а n любое целое число. Задача тут не принципиальная.

чего js ого

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

В гугл спрашивают как грабить дома? Понятно

Это какой то сюр. Кому в проде нужны эти алгоритмы? Гуглу и Яду?

@dmitrysapelnikov

Ай бұрын

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

@Stricken174

29 күн бұрын

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

Бляха, 10 лет работаю программистом. Подобную херабору решал последний раз на 2 курсе, тобишь лет 12 назад. Какие сверх разумы ставят эти задачи программистам ? У кого такие задачи возникают в ежедневной деятельности?) Все что вы узнаете из таких задач про программиста что он надроченый олимпиадник и на практике далеко не факт что будет с него толк. По факту проверка на то прорешал ли человек весь литкод)

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

@SayXaNow

Ай бұрын

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

Самый сложный ролик вышел 😅

Сформулировал задачу кривовато. Если её так выдать на собеседовании, часть собеседуемых посчитает, что нужно определить не только максимальную сумму, но и список домов из-за того, что это показано в начале подчеркиванием их и невнятно сформулированной задачей озвученной в это же время.

@SayXaNow

Ай бұрын

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

Ктооо придумывает эти задачи, ее так понять нельзя, а еще в коде написать.

@victorkochkarev2576

22 күн бұрын

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

Я обязательно выживу......

Это безсмыслица разбирать конкретные алгоритмы. Человеку либо дано программирование сложных задач, либо нет. В гугле кстати работают далеко не самые первоклассные программисты. Если пошариться по исходникам различных гугловских проектов - говнокода, том числе не оптимизированного дохера и больше.

Мне очень странно видеть чувака, который работает в гугле, но при этом рекламит курсы яндекс практикума......

📌 И не врите самому себе про Рабочий День 👀 kzread.info/dash/bejne/a2Zqz5Kld6iup5c.htmlsi=PHejZZ1pJ436F9Sr

Работает в Google в Lондоне и рекламирует курсы от яндекса)))) По-моему парнишка привирает)))

@loxloxloxloxl

Ай бұрын

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

@AlexanderShuraev

Ай бұрын

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

@igorratnik2357

Ай бұрын

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

@rtfdfhjrggth4220

Ай бұрын

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