Идеи динамического программирования: одномерные задачи, часть 1
Разбираем несколько классических задач динамического программирования с использованием одномерного массива и без него.
20К открытий21К показов
Динамическое программирование — способ решения задач путём разбиения их на подзадачи, которые, в свою очередь, используются для нахождения ответа исходной задачи. В этой статье мы разберём несколько классических задач динамического программирования, которые требуют для своего решения одномерный массив, либо, в некоторых случаях, можно даже обойтись без него.
Если вы не знакомы с динамическим программированием, посмотрите эту статью для начинающих.
Числа трибоначчи
Числа трибоначчи — это числовой ряд, начинающийся с трёх чисел 0, 0, 1, где каждое последующее число вычисляется как сумма трёх чисел перед ним:
Рассмотрим следующую задачу: дан массив чисел с порядковыми номерами чисел трибоначчи, например: [73, 10, 4, 15, 20, 7], числа в массиве не превышают 100, требуется вернуть массив, содержащий числа трибоначчи под указанными номерами: [73-е число трибоначчи, 10-е число трибоначчи, и так далее].
Если вы какое-то время работаете с языками программирования, то наверняка решали задачи нахождения факториала или степени числа через рекурсию. Попробуем применить такую же идею здесь:
Запускаем функцию с вычислением времени:
41-е число вычисляется 135 секунд. Кажется, что быстрее вручную посчитать числа, подставить в массив все 100 значений (ограничение задачи) и просто вернуть число на нужной позиции. В чём же проблема, как так получилось, что простой алгоритм работает так долго? Можно заметить, что следующее число вычисляется в 2 раза дольше, чем предыдущее. Давайте посмотрим на рекурсивное дерево вызовов:
Можно заметить, что при вычислении через рекурсию многие числа будут считаться по несколько раз, например, число 37 будет посчитано 6 раз. В замерах времени выше мы видели, что вычисление этого занимает 11 секунд, т.е. займёт половину времени от вычислений числа 41 — 66 секунд из 135.
Напрашивается решение проблемы — запоминать вычисленные значения и при необходимости просто их использовать. Давайте посмотрим, что получается в таком случае:
Пробуем выполнить новую функция с теми же входными данными:
Во-первых, мы видим, что выполнение теперь занимает доли миллисекунд. Во-вторых, замечаем понижение времени при каждом новом вызове. Это связано с оптимизациями компилятора JavaScript после определенного количества вызова кода. После пары вызовов время уменьшается на 0.1 миллисекунды (для моего компьютера), следовательно, 100 вычислений, которые нам требуются для исходной задачи, пройдут за 0.01 секунду.
Мы уже применили идеи динамического программирования — сохранили результат вычисления подзадачи для получения результата следующей задачи. Осталось вызвать это в цикле для исходного массива и получить ответ. Но что делать, если в вычисления закрадётся ошибка? Код с рекурсией отлаживать довольно сложно.
Давайте немного упростим решение за счёт идеи предварительного вычисления всех возможных вариантов. Это займёт очень мало времени, т.к. по условию задачи максимальное число — 100, и за счет идеи отказа от рекурсии. Будем считать так, как бы мы считали эти числа на листике, руками:
Поскольку идем, увеличивая число i
, и у нас изначально добавлено в массив tribonacciNumbersCache
три значения, то получение элементов i - 1
, i - 2
и i - 3
отработает без ошибок.
В 0
позиций массива tribonacciNumbersCache
— первое число трибонначи, главное не забыть вычитать единицу при получении значения.
Напишем решение исходной задачи — по массиву номеров получить массив с числами трибонначи:
В консоль будет выведено [2073693258389777400, 44, 1, 927, 19513, 7]
. Задача решена.
Задачи на LeetCode и CodeWars для тренировки вычислений чисел фибонначи, трибонначи.
Основные идеи
Мы использовали несколько подходов, типичных для динамического программирования:
- Определили, как из известных данных маленьких подзадач будет вычисляться следующая подзадача, т.е. с числами трибонначи из трёх значений будет вычисляться следующее значение. Это соотношение называется рекурсивным.
- Нашли исходные данные, чтобы можно было запустить наше вычисление.
- Определили, откуда брать ответ — вычитали единицу при обращении к элементу массива с посчитанными значениями.
Кузнечик и кувшинки
Рассмотрим следующую задачу: есть определённое количество кувшинок, расположенных в ряд, кузнечик стоит на первой из них. Он может прыгнуть на следующую кувшинку, либо перепрыгнуть через одну. Сколько существует разных способов (путей) добраться до последней кувшинки?
Рассмотрим вариант с 4-мя кувшинками. Можем перебрать варианты и посчитать, что до последней кувшинки можно добраться 3-мя разными способами:
Грустный кузнечик прыгает по кувшинкам
Рассмотрим сколько способов существует, чтобы добраться до каждой из кувшинок. До второй — 1 способ, до третьей — 2 способа: прыгнуть сразу на неё или прыгнуть с первой кувшинки. До четвёртой уже выяснили перебором, что существует 3 способа.
Можем заметить, что на четвёртую кувшинку мы можем прыгнуть только со второй или с третьей и что количество путей до неё равно количеству путей до второй кувшинки + количество путей до третьей кувшинки. Немного порассуждаем, почему так получается.
С третьей кувшинки на четвёртую есть только один путь — прыгнуть на неё, но при этом до третьей кувшинки было 2 разных пути. Соответственно, если мы двигаемся через третью кувшинку на четвёртую, то так и остается 2 разных пути это сделать. Аналогичные рассуждения можно провести для перемещения со второй на четвёртую кувшинку. Эти два случая будут разными путями, т.к. перед попаданием на четвёртой мы были на разных кувшинках, следовательно, количество путей надо просто сложить.
Аналогичные рассуждения можно провести для дальнейших перемещений, т.е. просто складываем количество путей до предыдущих двух кувшинок.
Понятно, как переходить от одной подзадачи к другой, осталось найти начальные условия. Возьмём за начальные условия количество вариантов попасть на вторую и третью кувшинки, т.е. 1 и 2.
Для нахождения начальных условий можно использовать более математический подход: ввести отрицательные кувшинки, количество путей до них будет 0, и использовать текущую позицию как последнее значение начальных условий. При таком подходе начальные условия будут 0 и 1. В текущей задаче будем использовать первый подход, но для более сложных задач имеет смысл использовать второй.
Получается следующая функция:
Задача решена, но можем заметить, что все значения, кроме двух последних, не используются, и упростить решение:
В цикле происходит смещение количества путей до i + 1 кувшинки. В начале way1 указывает на количество путей до первой кувшинки, way2 — до второй. После первого выполнения тела цикла way1 указывает на количество путей до второй кувшинки, way2 до третьей, и так далее. В конце выполнения цикла в way2 получится количество путей до n кувшинки.
Задача для практики на LeetCode
Максимальный(по сумме элементов) подмассив
Условие задачи: дан массив чисел, требуется найти непрерывную последовательность чисел с максимальной суммой.
Например, получен такой массив:
Рассмотрим идею решения. Начнём суммировать значения в этом массиве слева направо. Просуммировав два первых элемента: 2 — 5 = −3, получим отрицательное число. Если добавить это число к следующему, то оно уменьшит его, независимо от того положительное оно или отрицательное. Просуммировав следующие 3 элемента 2 + 2 — 1 = 3, получим положительное значение, которое при добавлении к следующему увеличит сумму с ним в любом случае.
Т.е. мы идём слева направо, суммируя элементы, если сумма становится отрицательной, то игнорируем подсумму, если положительной, то прибавляем дальше:
В процессе этих вычислений при каждом прибавлении сравниваем число с переменной, в которой хранится максимальное подсумма.
Рассмотрим решение в коде:
Рассмотрим массив arrayOfSums, на каждом шаге итерации:
Видим, что максимальное значение 7. Это и будет ответ в текущей задаче.
В решении мы находим только максимальную сумму подмассива, но не находим саму часть массива. По рассмотренному массиву arrayOfSums и логике решения задачи довольно очевидно, как найти требуемый подмассив: находим 7 в массиве arrayOfSums, это будет конец подмассива. Берём слева все положительные числа, самое левое из списка положительных чисел — начало подмассива.
В текущем случае это сумма от второго до седьмого элемента (при отсчёте массива от 0). Подмассив arrayOfSums [2, 4, 3, 6, 5, 7]
, подмассив исходного массива nums [2, 2, -1, 3, -1, 2]
.
Реализуем эту идею в коде:
Задача для практики на LeetCode
Заключение
Мы рассмотрели несколько простых задач динамического программирования, желаю успехов в освоении этого непростого, но очень интересного подхода к решению задач.
20К открытий21К показов