Алгоритм нахождения минимальной цены, чтобы пройти через массив

Question

Я много думал о следующей проблеме:

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

Например, если массив выглядит так: [2,1,4,2,5] самый дешевыйдо конца можно добраться до 10: мы посещаем индексы 1-> 2-> 4-> 5 и должны заплатить 2 + 1 + 2 + 5 = 10 , чтоэто самый дешевый способ.Пусть f (i) будет самой дешевой ценой для индекса i .Это мы можем легко вычислить за O (n) время с помощью динамического программирования, поняв, что f (i) = arr [i] + min (f (i-1), f (i-2)))

Но вот поворот: массив обновляется несколько раз, и после каждого обновления мы должны быть в состоянии сказать в O (logn) время, что является самым дешевым способомв данный момент.Обновление массива происходит путем указания индекса, который будет изменен, и номера, на который он будет изменен.Например, обновление может быть arr [2] = 7 , изменяя наш примерный массив на [2,7,4,2,5] .Теперь самый дешевый способ будет 11.

Теперь, как мы можем поддержать эти обновления в O (logn) времени?Есть идеи?

Вот то, что я до сих пор придумал: во-первых, я бы создал массив f для динамического программирования, как описано ранее.Я бы сохранил содержимое этого массива в дереве сегментов s следующим образом: s (i) = f (i) - f (i-1) .Это позволило бы мне обновлять интервалы f (добавляя константу к каждому значению) за O (logn) времени и запрашивать значения по данному индексу в O (logn) время.Это может пригодиться, поскольку после некоторых обновлений часто случается так, что все значения в f необходимо будет увеличивать на постоянную после некоторого заданного индекса в f .Поэтому, запрашивая значение s (n) в дереве сегментов после каждого обновления, мы получим нужный нам ответ.

Однако после обновления могут произойти разные вещи:

1. Необходимо обновить только одно значение в f .Например, если [2,1,4,2,5,4,9,3,7] изменяется на [2,1,9,2,5,4,9,3, 7] only f (3) необходимо будет обновить, так как в любом случае ни один из самых дешевых способов не прошел 3. индекс.
2. Все значения в f после того, как данный индекс необходимо обновить константой.Это то, для чего подходит дерево сегментов.
3. Каждое другое значение в f после того, как данный индекс должен быть обновлен константой.
4. Нечто более случайное.

Answer 1

Хорошо, мне удалось решить проблему самостоятельно, поэтому я решил поделиться с вами решением.:)

Я был на правильном пути с динамическим программированием и деревом сегментов, но я неправильно подал дерево сегментов в моих предыдущих попытках.

Вот как мы можем поддерживать обновленияв O (logn) время: Идея состоит в том, чтобы использовать двоичное дерево сегментов, где листья дерева представляют текущий массив, а каждый узел хранит 4 различных значения.

1. v1 = Наименьшая стоимость, полученная от крайнего левого потомка до крайнего правого потомка
2. v2 = Наименьшая стоимость, получаемая открайний левый потомок второго правого потомка
3. v3 = Наименьшая стоимость перехода от второго левого потомка к крайнему правому потомку
4. v4 =Наименьшая стоимость перехода от второго левого потомка ко второму правому потомку

Под потомками я подразумеваю потомков узла, которые также покидают.

При обновлении массива мы обновляемзначение на листе, а затем все его предки до корня.Поскольку в каждом узле мы уже знаем все эти 4 значения его двух дочерних элементов, мы можем легко вычислить новые 4 значения для текущего родительского узла.Просто для примера: v1_current_node = min (v2_leftchild + v1_rightchild, v1_leftchild + v1_rightchild, v1_leftchild + v3_rightchild) .Все остальные три значения можно рассчитать аналогичным образом.

Поскольку для каждого листа есть только O (logn) предков, а все 4 значения рассчитываются в O (1) время, необходимое для обновления всего дерева O (logn) .

Теперь, когда мы знаем значения 4 для каждого узла, мыАналогичным образом можно рассчитать наименьшую стоимость от первого до n : -го узла, используя узлы с наивысшими степенями 2 на нашем пути в дереве, которые складываются в п .Например, если n = 11 , мы хотим знать наименьшую стоимость от первого до одиннадцатого узла, и это можно сделать, используя информацию об узле, который покрывает листья 1-8 ,узел, который покрывает листья 9-10 и узел листа 11 .Для всех этих трех узлов мы знаем описанные значения 4 и можем аналогичным образом объединить эту информацию, чтобы выяснить ответ.Самое большее, для этого нам нужно рассмотреть O (logn) узлов, чтобы это не было проблемой.