Это первая моя статья по подобной тематике, так что просьба отнестись с пониманием. Буду рад любым комментариям и замечаниям.
Думаю, многие из вас слышали, а многие даже сталкивались с таким методом решения неких задач, как метод динамического программирования. Для тех, кто не знает, вот определение Википедии:
Довольно хорошее и понятное объяснение, но давайте лучше возьмем пример. Думаю, самое простое, что приходит в голову, это числа Фибоначчи. Для нее заданы некоторые исходные данные – A[1]=1, A[2]=1, в после элемент A[i]=A[i-1]+A[i-2]. При этом A[i] часто называют состоянием, а некое отношение относительно предподсчитанных данных – переходом. В данном случае из A[i] есть 2 перехода – в A[i-1] и в A[i-2]. Количество переходов может меняться в зависимости от задачи.
Но ведь динамическое программирование не просто так используют. А именно потому, что оно позволяет иногда очень значительно сократить время решения какой-либо задачи, что иногда, при большим объемах входных данных, бывает очень критично. И я хочу показать одну такую задачу, которую встретил на Зональной Олимпиаде Школьников в этом году. Дословно условие не помню, но вот общий смысл:
Итак, чтобы узнать значение элементов в какой-либо строке, нам надо знать значения элементов во всех строках выше нее. Самое простое решение, которое приходит на ум, это для каждого элемента просто взять и пройтись по всем элементам в треугольнике выше него, считая сумму. Да, так можно сделать, когда время не критично или когда ограничения на N и M небольшие, т.к. такой алгоритм работает за асимптотику порядка O(N4) (если принимать N=M). Т.е. даже при N=M=100 это будет работать порядка 5-10 секунд (зависит от компьютера), я уже молчу про N=M=2000. Значит, нам нужно как-то это дело ускорять. А давайте сделаем вот как. У нас есть треугольник, который надо подсчитать. И у нас есть предподсчитанные треугольники для всех элементов выше него. Так давайте составим новый треугольник, используя уже рассчитанные! Смотрим рисунок:
Т.е. если нам нужно рассчитать треугольник с началом в A[i,j], тогда он будет считаться по формуле:
A[i,j]=(A[i-1,j]+2*A[i-1,j-1]+2*A[i-1,j+1]-2*A[i-2,j]) mod K. (где mod K — взять по модулю K)
Мы отнимаем треугольник A[i-2,j] т.к. это область пересечения двух треугольников A[i-1,j-1] и A[i-1,j+1] и в противном случае мы посчитали бы ее 2 раза. Кстати, подумайте сами, почему мы умножаем на 2 некоторые значения.
Общая идея у этой задачи вот такая. Попробуйте сами написать ее решение (в ней есть несколько нюансов, которые я предлагаю вам найти самим) и проверить ее с помощью обычного переборного алгоритма на разных тестах. Если что непонятно – обращайтесь, постараюсь помочь, хотя, надо признаться, сам я в этом деле далеко не профи и решить могу далеко не все задачи, но на кое-что способен ;-)
Думаю, многие из вас слышали, а многие даже сталкивались с таким методом решения неких задач, как метод динамического программирования. Для тех, кто не знает, вот определение Википедии:
Идея динамического программирования состоит в разбиении задачи на несколько независимых подзадач, решении каждой из них, а затем вычислении исходного результата. Для решения подзадач этот же алгоритм применяется рекурсивно. При этом для каждой подзадачи запоминается вычисленный ответ, и если на каком-то шаге подзадача встретилась второй раз, то вычисления для неё не производятся.
http://ru.wikipedia.org/wiki/Динамическое_программирование
Довольно хорошее и понятное объяснение, но давайте лучше возьмем пример. Думаю, самое простое, что приходит в голову, это числа Фибоначчи. Для нее заданы некоторые исходные данные – A[1]=1, A[2]=1, в после элемент A[i]=A[i-1]+A[i-2]. При этом A[i] часто называют состоянием, а некое отношение относительно предподсчитанных данных – переходом. В данном случае из A[i] есть 2 перехода – в A[i-1] и в A[i-2]. Количество переходов может меняться в зависимости от задачи.
Но ведь динамическое программирование не просто так используют. А именно потому, что оно позволяет иногда очень значительно сократить время решения какой-либо задачи, что иногда, при большим объемах входных данных, бывает очень критично. И я хочу показать одну такую задачу, которую встретил на Зональной Олимпиаде Школьников в этом году. Дословно условие не помню, но вот общий смысл:
Есть матрица чисел A размера NxM и число K. Задана первая ее строка – A[1,1]..A[1,M]. После этого для каждого элемента, стоящего ниже первой строки, значение определяется как сумма всех элементов в треугольнике выше него по модулю K. Требуется вывести последнюю строчку этой матрицы A[N,1]..A[N,M]. Ограничения: 1 ≤ N,M ≤ 2000; 2 ≤ K ≤ 109.
Итак, чтобы узнать значение элементов в какой-либо строке, нам надо знать значения элементов во всех строках выше нее. Самое простое решение, которое приходит на ум, это для каждого элемента просто взять и пройтись по всем элементам в треугольнике выше него, считая сумму. Да, так можно сделать, когда время не критично или когда ограничения на N и M небольшие, т.к. такой алгоритм работает за асимптотику порядка O(N4) (если принимать N=M). Т.е. даже при N=M=100 это будет работать порядка 5-10 секунд (зависит от компьютера), я уже молчу про N=M=2000. Значит, нам нужно как-то это дело ускорять. А давайте сделаем вот как. У нас есть треугольник, который надо подсчитать. И у нас есть предподсчитанные треугольники для всех элементов выше него. Так давайте составим новый треугольник, используя уже рассчитанные! Смотрим рисунок:
Т.е. если нам нужно рассчитать треугольник с началом в A[i,j], тогда он будет считаться по формуле:
A[i,j]=(A[i-1,j]+2*A[i-1,j-1]+2*A[i-1,j+1]-2*A[i-2,j]) mod K. (где mod K — взять по модулю K)
Мы отнимаем треугольник A[i-2,j] т.к. это область пересечения двух треугольников A[i-1,j-1] и A[i-1,j+1] и в противном случае мы посчитали бы ее 2 раза. Кстати, подумайте сами, почему мы умножаем на 2 некоторые значения.
Общая идея у этой задачи вот такая. Попробуйте сами написать ее решение (в ней есть несколько нюансов, которые я предлагаю вам найти самим) и проверить ее с помощью обычного переборного алгоритма на разных тестах. Если что непонятно – обращайтесь, постараюсь помочь, хотя, надо признаться, сам я в этом деле далеко не профи и решить могу далеко не все задачи, но на кое-что способен ;-)
