Мне кажется, я понимаю A. Решение Джордана теперь заключается в чтении структур данных и, в частности, Сегментных деревьев с отложенными обновлениями .
Тем не менее, есть много идей о проблеме, которая должна быть сделана первой:
Подготовка:
- Удобно сортировать гнезда по высоте. После того, как это сделано, сама высота не имеет значения, только положение в массиве гнезд. (то есть все высоты будут нормализованы как целые числа 0,1,2,3,4 ...). Это означает, что, как только гнезда отсортированы, мы можем забыть об их фактической высоте.
- Отслеживать индекс гнезда в исходном массиве, потому что это необходимо для определения относительного положения слева / справа других гнезд. по отношению к этому. На изображении выше индекс показан красным, а высота - черным.
Теперь общая стратегия определения общего количества действительных путей будет:
- Рассчитайте количество способов, которыми может быть достигнут любой Гнездо (k) (0 <= k <N, k - позиционный индекс слева направо) как <strong>конечный пункт назначения и суммируйте все эти пути (который будет окончательным ответом). Назовите количество способов Гнездо (k) может быть достигнуто как конечный пункт назначения W (k)
Поскольку любое гнездо может быть достигнуто только из более низких гнезд , если мы пересечем гнезда в порядке возрастания (т.е. упорядочены по высоте), мы сможем рассчитать W (k) на основе всех ранее вычисленных значений. Это стандартный подход к динамическому программированию c.
Теперь подумайте о допустимых способах достижения Nest (k) в качестве конечной точки:
- Начните с Гнездо (k) и оставайтесь там, что дает 1 возможность
- Начните с любого ранее рассчитанного пути через более низкое Гнездо (i) , где i> k и начальное гнездо для этого пути имело индекс j, где k
- Начинается с любого ранее рассчитанного пути через нижнее гнездо (i) , где i и у начального гнезда для этого пути был индекс j, где i <= j <k. </li>
Это может быть визуализировано как для любого допустимого способа, которым стартовое гнездо должно находиться между конечным пунктом назначения и гнездом, из которого был достигнут этот пункт назначения.
Например, возьмите Гнездо (1) на снимке с высотой = 6. Его можно получить из любого через Гнездо (4) , которое имеет высоту = 5, для которого индекс начального гнезда находится между финальным Гнездо (1) и Гнездо (4) включительно. Обратите внимание, что диапазон включительно, потому что он также может быть напрямую доступен из Nest (4) . Однако его нельзя достичь тем способом, который начинался с Nest (0) и переходил к Nest (4) , потому что тогда два последних прыжка были бы с одной и той же стороны от старта. гнездо, которое не допускается.
Теперь назовите количество путей от конкретного начального гнезда Гнездо (i) , которое заканчивается справа R (i) и число путей, которые заканчиваются слева L (i) и предполагаем, что мы рассчитали все эти возможные пути для более низких гнезд.
Тогда:
- W (k) = 1 + сумма ([R (j) для j в k + 1 ... N-1]) + сумма ([L (j) для j в 0 ... k-1])
Этот расчет имеет временную сложность O (N) (для каждого k ) так что нужна оптимизация, но мы к этому придем позже. Сначала нам нужно понять, как отслеживать R (j) и L (j) .
Это снова можно сделать с помощью динамического программирования c подход:
Скажем, мы знаем текущее количество путей от Гнездо (i) , которые заканчиваются справа R (i) . Каждый раз, когда мы сталкиваемся с новым гнездом слева от Гнездо (i) , количество путей, которые заканчиваются слева L (i) увеличивается на текущий R ( я) . Это происходит потому, что каждый путь, который заканчивался направо, получает новую опцию go на один шаг дальше к новому гнезду слева. Разумеется, верно и обратное: R (i) = L (i) , если встречается гнездо справа.
Таким образом, мы можем извлечь еще два расчеты:
для i в 0 ... k-1: R (i) + = L (i) для i в k + 1 ... N- 1: L (i) + = R (i) Первоначально число путей как L (i), так и R (i) должно быть установлено на 1, чтобы учесть прямой возможность go от начального гнезда до гнезда назначения.
Для каждого гнезда, которое расположено слева, увеличьте число правильных путей, как описано выше, и то же самое для каждого гнезда, которое расположено к правильно.
Однако, опять же, это требует O (N) операций.
Для справки, очень простая python программа, которая выполняет вычисления выше (что дает правильное результаты, но медленно O (N ^ 2)) перечислены ниже:
def solution(H):
MOD = 1000000007
N = len(H)
nests = [(height, index) for index, height in enumerate(H)]
nests.sort()
dp_left = [0] * N
dp_right = [0] * N
total = 0
for nest in nests:
index = nest[1]
# Add 1 way for the current nest
total += 1
# Add all possible ways reaching this nest from the left
for i in range(index):
total += dp_left[i]
total %= MOD
# Add all possible ways reaching this nest from the right
for i in range(index + 1, N):
total += dp_right[i]
total %= MOD
# Initialize left and right ways to 1 for the current nest
dp_right[index] = 1
dp_left[index] = 1
# Update the right possible ways for nests to the left
for i in range(index):
dp_right[i] += dp_left[i]
dp_right[i] %= MOD
# Update the left possible ways for nests to the right
for i in range(index + 1, N):
dp_left[i] += dp_right[i]
dp_left[i] %= MOD
return total % MOD
Теперь, чтобы достичь O (N Log (N)) сложность времени, мы должны были бы найти способ улучшить временную сложность вычислений 1, 2 и 3 с O (N) до O (log (N)) .
Теперь вот где В игру вступает концепция Деревьев ленивых сегментов , которые могут Именно так.
По сути, как обновления, так и запросы могут быть преобразованы в операции O (log (N)), как объяснено.
Теперь для реализации этого еще предстоит решить некоторые технические детали. В частности, для выполнения отложенных обновлений, поскольку применяемые обновления не являются постоянным значением для каждого гнезда, а зависят от индекса обновляемого гнезда. См. этот вопрос для справки.
Вот ссылка на мое решение , основанное на A. Решение Джордана переписано в Swift с большим количеством кода и упрощений.