Comments 13
Содержание статьи на высоте, но...
Пожалуйста, читайте свои статьи, когда пишете. Например, было бы замечательно, если бы Вы исправили «отнестись с понимание», «метод динамического программирование», написали степень через <sup>, а индексы через <sub>.
Пожалуйста, читайте свои статьи, когда пишете. Например, было бы замечательно, если бы Вы исправили «отнестись с понимание», «метод динамического программирование», написали степень через <sup>, а индексы через <sub>.
Честно говоря, когда увидел название, подумал, что будет описан случай применения динамического программирования где-нибудь кроме олимпиадного программирования...
А так, статья в целом интересна, хотя описываемую задачу я бы решил по-другому :)
А так, статья в целом интересна, хотя описываемую задачу я бы решил по-другому :)
Ну, иногда и на практике встречаются олимпиадные задачи, а в ДП главное - уловить суть и практика, ну и мозги.
Еще можно считать как сумму треугольника, который выше него и двух диагоналей, которые надо тоже предподсчитывать. Возможно, это немного улучшит асимптотику, но ест дополнительную память, так что я решил такой способ описать.
Еще можно считать как сумму треугольника, который выше него и двух диагоналей, которые надо тоже предподсчитывать. Возможно, это немного улучшит асимптотику, но ест дополнительную память, так что я решил такой способ описать.
В английской википедии (http://en.wikipedia.org/wiki/Dynamic_programming) неплохой список задач, при решении которых используется динамическое программирование. Я сам с русской терминологией практически не знаком, поэтому переводить не берусь.
От себя добавлю, что исторически сложившийся термин "динамическое программирование" (как и линейное или математическое) к программированию отношения не имеет, а подразумевает оптимизацию, т.е. суть ДП - именно поиск "хорошей" рекурсии для решения поставленной задачи.
В программировании же способ оптимизации рекурсии средством запоминания значений функции в некоторых точках называется memoization, и в случае функций, значение которых зависит только от их аргументов, решается компьютером. В некоторых языках (maple, к примеру) этот функционал встроен, в некоторых легко строится на ленивых вычислениях, в других существуют готовые библиотеки.
От себя добавлю, что исторически сложившийся термин "динамическое программирование" (как и линейное или математическое) к программированию отношения не имеет, а подразумевает оптимизацию, т.е. суть ДП - именно поиск "хорошей" рекурсии для решения поставленной задачи.
В программировании же способ оптимизации рекурсии средством запоминания значений функции в некоторых точках называется memoization, и в случае функций, значение которых зависит только от их аргументов, решается компьютером. В некоторых языках (maple, к примеру) этот функционал встроен, в некоторых легко строится на ленивых вычислениях, в других существуют готовые библиотеки.
Ну, английский на достаточном уровне знают не все.
Меня учили, что это именно так называется. И не всегда динамика - это ленивые вычисления, может, следующую статью я посвящу именно такой задаче, где динамика - это не ленивые вычисления, а поиск наилучшего варианта из некоего набора.
Да и я считаю, что программист должен сам уметь писать такие вещи, потому что странно иногда видеть программистов, которые могут писать большие проекты, знают кучу библиотек, а реализация, например, кучи или написание быстрой сортировки вызывает у них проблемы.
Меня учили, что это именно так называется. И не всегда динамика - это ленивые вычисления, может, следующую статью я посвящу именно такой задаче, где динамика - это не ленивые вычисления, а поиск наилучшего варианта из некоего набора.
Да и я считаю, что программист должен сам уметь писать такие вещи, потому что странно иногда видеть программистов, которые могут писать большие проекты, знают кучу библиотек, а реализация, например, кучи или написание быстрой сортировки вызывает у них проблемы.
> Ну, английский на достаточном уровне знают не все.
Тогда попытаюсь таки привести несколько примеров
> применения динамического программирования
> где-нибудь кроме олимпиадного программирования
Из простых алгоритмов: задача о рюкзаке (ранце), кратчайшие пути в графе (Floyd,Warshall), перенос слов (Knuth), оптимальная последовательность умножения матриц, алгоритм Левенштейна, поиск лучших общих подпоследовательностей.
Надеюсь, понятно, что пракическое применение ДП, как и любой математической дисциплины, не исчерпывается какой-либо специфической областью. Чтоб назвать пару - сегодня ДП является широко используемым подходом к решению частных случаев NP-полных задач, а также имеет широкое применение в экономике и финансовых дисциплинах.
> Меня учили, что это именно так называется.
Решение задачи, описанное вами в статье (от условия до формулы) называется динамическим программированием. Имплементация, которую вы имеете ввиду здесь
> Попробуйте сами написать ее решение
к нему уже не относится, и в общем случае представляет из себя или простую итерацию (bottom up - если вы можете рассчитать базу рекурсии), или рекурсию с memoization (top down) [хвостовую рекурсию причислим к первой категории, хотя в ДП она практически неприменима].
> И не всегда динамика - это ленивые вычисления
Не совсем понял, но не думаю, что это важно.
> Да и я считаю, что программист должен сам уметь
> писать такие вещи, потому что странно иногда
> видеть программистов, которые могут писать
> большие проекты, знают кучу библиотек, а
> реализация, например, кучи или написание быстрой
> сортировки вызывает у них проблемы.
Каждому человеку нужно место в жизни :)
Тогда попытаюсь таки привести несколько примеров
> применения динамического программирования
> где-нибудь кроме олимпиадного программирования
Из простых алгоритмов: задача о рюкзаке (ранце), кратчайшие пути в графе (Floyd,Warshall), перенос слов (Knuth), оптимальная последовательность умножения матриц, алгоритм Левенштейна, поиск лучших общих подпоследовательностей.
Надеюсь, понятно, что пракическое применение ДП, как и любой математической дисциплины, не исчерпывается какой-либо специфической областью. Чтоб назвать пару - сегодня ДП является широко используемым подходом к решению частных случаев NP-полных задач, а также имеет широкое применение в экономике и финансовых дисциплинах.
> Меня учили, что это именно так называется.
Решение задачи, описанное вами в статье (от условия до формулы) называется динамическим программированием. Имплементация, которую вы имеете ввиду здесь
> Попробуйте сами написать ее решение
к нему уже не относится, и в общем случае представляет из себя или простую итерацию (bottom up - если вы можете рассчитать базу рекурсии), или рекурсию с memoization (top down) [хвостовую рекурсию причислим к первой категории, хотя в ДП она практически неприменима].
> И не всегда динамика - это ленивые вычисления
Не совсем понял, но не думаю, что это важно.
> Да и я считаю, что программист должен сам уметь
> писать такие вещи, потому что странно иногда
> видеть программистов, которые могут писать
> большие проекты, знают кучу библиотек, а
> реализация, например, кучи или написание быстрой
> сортировки вызывает у них проблемы.
Каждому человеку нужно место в жизни :)
А Вы не забыли в формуле для A[i,j] взять по модулю K?
Задачка и решение красивое. Спасибо за статью!
Задачка и решение красивое. Спасибо за статью!
Да, еще вопрос - нужно решение выкладывать на C++ или Delphi?
Помню когда занимался олимпиадным программированием, то динамическое программирование всегда труднее давалось, тех же графов например. Много интересных задач было, особенно где состояние не удается так интуитивно определить. Например классная задача - вычислить колличество способов расставить N шахматных королей на доске, что-бы они не били друг друга
p.s. уже три года работаю - ни разу в работе не приходилось применять :)
p.s. уже три года работаю - ни разу в работе не приходилось применять :)
Sign up to leave a comment.
Динамическое программирование на практике.