Динамическое программирование сверху и снизу

Скорость рекуррентного вычисления чисел Фибоначчи.
Проблема повторных вычислений.
Подход динамического программирования состоит в том, чтобы решить каждую подзадачу только один раз, сократив тем самым количество вычислений
Динамическое программирование сверху и снизу.
Курс молодого бойца по информатике (Язык Си).
cs.mipt.ru/c_intro

[@rkgrachel]

Красавчик! Всем б таких преподов в школы/универы.

[@vladimirpitchkurov4483]

очень круто! спасибо вам! много полезного узнал. а про кеширование результатов рекурсивной функции - вообще огонь! толи еще будет))

[@user-xb7wq5kp5l]

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

[@poigrushkin9433]

Это нечто! Лучшее, что я видел

[@lorikbirrov6572]

Полностью поддерживаю!)

[@user-rq1vm3hn9l]

Потрясное объяснение, вы лучший

[@user-dl3zo8xf7g]

Я таксист, но очень интересно)).

[@vip51000]

еще не поздно стать программистом

[@user-dl3zo8xf7g]

@@vip51000 уже)))

[@IonIndi]

@@user-dl3zo8xf7g история с хорошим окончанием :)))

[@Ruslan-nj5zw]

в каком возрасте вы решили быть программистом?

[@vartan_babayan_4388]

очень круто, очень красиво...

[@firstplayer758]

Пожалуй лучшее объяснение, и даже не важно что не на родном С

[@BidonNadoev]

Лучшее объяснение ДП 👍

[@VideoEffekts]

human resource machine был такой уровень только там примерно такой код должен быть. int f[2] = { 0,1 }; for (int i = 0; i < 40; i++) { f[i % 2] = f[0] + f[1]; printf(" %d ", f[i % 2]); }

[@user-vp3ml5qq7l]

ого как здорово. Спасибо

[@user-dc5pp3pp5r]

Спасибо!

[@morrigan_ghost]

восторг.

[@GOBBANIMATION]

Круто👍

[@befuture_ru]

👍👍👍

[@MC-RAY]

Желаю всем такого препода

[@user-vu8pl8zl7h]

Метод снизу кажется логически более простым для осознания так сказать... но блин тот который сверху, с рекурсией, очень красиво получилось, я долго сидел осознавал) Вот для питона что у меня получилось: #динамический метод с рекурсией(сверху) F=[0]*100 def fib(n): if n

[@Amselber]

cache = {} def fib(n): try: return cache[n] except KeyError: if n

[@Amselber]

def fib(n): fibs=[0, 1] for i in range(2, n+1): fibs.append(fibs[i-1] + fibs[i-2]) return fibs[n]

[@Devnbp1]

сразу видно челы даже про декораторы никогда не слышали

[@veresivan]

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

[@metrondir132]

Добрый вечер. Вы можете помочь по питону?

[@instrumentalcovers4397]

А почему компилятор не выдает ошибку, связанную с int Fib[n+1] ? Массив же статический, значит, n должно быть известно

[@Ma_X64]

В новом стандарте можно так делать. Но только для локальных переменных.

[@VirtuousSaint]

Я тоже удивлен. У меня С11 тож в сборке mingw, и мой компилятор такое не пропускает. Поправочка, компилятор не пропускает, если попытаться в той же строке инициализировать все элементы в нули. Если просто объявить массив, то можно :\

[@starhighway4602]

Начиная со стандарта С99 можно делать такие определения внутри функции. Память в этом случае выделяется на стеке, в отличие от malloc, который выделяет в куче.

[@julesbois2122]

В чём может быть проблема, если и с кешем, и без кеша время выполнения одинаково (первые два рассматриваемых случая)? Windows, MinGW, gcc

[@johannesgarin6559]

меня, в свое время, воодушевил этот пример, что так лихо можно кэшировать и настолько ускорять производительность кода. Смущала только затраченная память, потом дошел до того, что не обязательно кэшировать в память, можно просто переменными передавать нужные параметры. А сегодня увидел такое: Python3 def fib(n): if n == 0: return 0 elif n == 1: return 1 else: return n + fib(n-1) Вопрос: зачем нужно было вызывать функцию два раза в примере из видео? Шутка, код выше - это модификация нахождения факториала и она работает не правильно 😂 Но можно сделать так: def fib(n): if n

[@lorensstudio3233]

Я в этом ничего не понимаю, решил просто так послушать и на 3:02 не понятно, почему 1+0 возвращает 0?

[@franxxinatra1228]

Бывает, оговорка. Сказал одно, а на доске другое.

[@alexs7952]

Чёта я не догнал, чем второй (последний) метод лучше рекурсии с кешированием, когда у него производительность хуже, цикл в цикле, плюс массив создаётся в каждом вызове fib_dynamic

[@alexs7952]

@@saltylungs о каком вложенном цикле идёт речь - функция fib_dynamic() содержащая цикл в строке 19 выполняется в цикле в строке 26

[@artur1998g]

Ну с кешированием однозначно быстрее, там на тот же самый fib_dynamic(500) цикл прогонится 498 раз, а на верхнюю функцию, если до этого вызывались fib 499, то и вычислиться с 2 вызовыми. fib(500) = fib (499) и fib(498). По ощущением fin_dynamic это вообще не относится к динамическому программированию, конкретно под термин "решить каждую подзадачу только один раз". Либо я чего-то не понимаю. Но сложность функции find_dynamic получается O(n-2), даже если были известны до этого вычисления.

[@user-fc3gh1rb7w]

хммм... А если такое дерево? ) int Fib(int n) { while (n>0) { Fib(--n); } return n; }

[@elderlyoparysh2800]

кроме того еще и стек переполниться может в первом варианте программы.

[@criterrors]

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

[@kurbanmurad]

Інколи завдяки рекурсії зручно "дочекатися" (встановлюючи інтервали очікування) "чогось", на що не зручно повісити listener чи observer. На практиці це виручає наприклад в JavaScript, коли використовуються кілька різних бібліотек і динамічно додаються елементи в DOM. Такий собі спосіб async await))

[@user-ee3bf1uq2f]

А разве cache[n] = fib(n-1) + fib(n-2) нельзя заменить на cache[n] = fib(n-1) + cache[n-2]?

[@nicholasspezza9449]

да, можно. Так будет более оптимизированно.

[@commoncriminal923]

What

[@NewMrCricket]

10:08 "глубина погружения все равно большая" - неправда, глубина всего одного вызова

[@ukravenger3924]

нет, макс. глубина вызова ~n, см. на доску

[@NewMrCricket]

Имелся ввиду пример с fib(1=>50), всё в кеше

[@ukravenger3924]

@@NewMrCricket при чем кэш, если речь шла о стэке? И глубина более одного вызова.

[@NewMrCricket]

@@ukravenger3924 Строка 17: вызываем fib(1) => fib(50), значит при n==40 (например), мы имеем в кеше результаты всех предыдущих n => fib(1-39) То есть при вызове, например, fib(40), мы а) в строке 9 не находим значение для n==40 в кеше, затем б) в строке 10 вызываем fib(39) => то есть уходим на один вызов в стеке глубже => находим значение для n==39 в кеше (строка 11), и возвращаемся в fib(40) в) в строке 10 вызываем fib(38) => то есть уходим на один вызов в стеке глубже => находим значение для n==38 в кеше (строка 11), и возвращаемся в fib(40) Значит, при вызове fib(40) мы дважды спустились по стеку на глубину == 1 и вернулись. А в начале 11й минуты автор говорит "с кешированием или без, память мы не экономим, глубина погружения все равно большая", но ведь в его примере глубина погружения == 1? (Ну, или 2, смотря как считать)

[@ukravenger3924]

@@NewMrCricket в этом случае повезло с предыдущими вызовами, но так везет далеко не всегда ) Тимофей, скорее всего, имел в виду общий случай.

[@izualno_oname7234]

Почему мне это попало в рекомендации? Что это за убогий подход вообще.. Всего нужно 2 кеш числа, потому что каждая N итерация будет затрагивать только лишь N-1 и N-2, и при следующем витке происходит смещение итератора и замена N-2 на N, оставляя уже для следующей суммы опять N-1(бывшая N), и N-2(бывшая N-1).