Эта статья возникла из личного публичного аккаунта:TechFlow, оригинальность это не просто, прошу внимания
Сегодня17 статей по алгоритмам и структурам данныхСтатья также является шестой по теме динамического программирования.
Сегодня давайте рассмотрим очень классическую задачу динамического программирования. Насколько она классическая? Я подумал об этом, наверное, это была самая ранняя задача динамического программирования, которую я решил в своей жизни, так что я до сих пор помню ее название.
тема
Это вопрос системы перехвата ракет.Говорят, что некая страна разработала систему перехвата ракет, которая может перехватывать ракеты вражеских стран. Ракеты разной дальности летят на разной высоте при выбросе.Эта система перехвата можетБлокировать от низкого к высокомуВлетающая ракета, но высота ее следующего перехвата должна быть больше или равна предыдущей высоте,Можно только вверх, а не вниз. Итак, позвольте мне спросить, если мы обнаружим высоту всех ракет, запущенных вражескими странами, сколько из них мы сможем перехватить самое большее?
Я так много говорил о смысле темы выше.На самом деле, я могу обобщить ее в одном предложении, то есть найти последовательностьсамая длинная неубывающая подпоследовательностьдлина. Также есть вопросы, чтобы найти самую длинную не возрастающую подпоследовательность в обратном порядке, что означает то же самое.
решение грубой силы
Рассмотрим пример: предположим, что вражеская страна отправила всего 8 ракет, а их высоты полета: [65, 158, 170, 299, 300, 155, 207, 389].
Достаточно легко найти ответ, посмотрев на него глазами, ответ должен быть [65, 158, 170, 299, 300, 389] всего 6 ракет, из которых 155 и 207 невозможно перехватить. Предполагая, что мы не знаем, что это алгоритм динамического программирования, как нам найти решение?
Как обычно, начнем с самого простого метода грубой силы. Самый жестокий метод — перечислить все возможные состояния числа n.Для каждого элемента есть два состояния: одно — брать, другое — не брать. Тогда для массива из n элементов, очевидно, всего будет
иная возможность. тогда мыОпределите, является ли каждая возможность законной в свою очередь, оставьте тот, у которого самая длинная допустимая длина.
Конечно, мы также можем использовать поиск, мы можем исключить недопустимые комбинации в процессе поиска, но в крайних случаях, например, когда весь массив находится в порядке возрастания, все случаи все равно будут пронумерованы, поэтому общая сложность все еще
. Для нас это явно неприемлемо.
Так как же нам найти лучшие решения?
перцептивное знание
Мы наблюдаем и размышляем над этой проблемой, мы обнаружим, что в этой проблемеРешения для разных масштабов должны быть одинаковыми. Если метод может решить последовательность длиной 1000, то, естественно, он может решить и последовательность длины 5, и наоборот. Так что мы не можем не думать, тогда мы начнем с самого простого случая, можем ли мы найти решение?
Мы начнем с массива длины 1, и, очевидно, ответ будет определенным, то есть 1.
А если длина равна 2? Например [65, 158], тогда нам нужно судить, может ли второе число следовать за первым числом, то есть является ли второе число больше или равно первому числу, если да, то ответ равен 2, иначе , ответ по-прежнему равен 1, например [65, 34], а самая длинная последовательность может быть только [65] или [34].
А если 3 числа? Ситуация будет немного сложнее. Мы можем проанализировать ее в обратном порядке. Если ответ равен 3, то есть только один случай возрастания последовательности. Если ответ равен 2, то есть два случая. Один из них состоит в том, что последовательность возрастает. первые два элемента составляют приращение, например [20, 30, 10], во втором случае один из первых двух элементов и третье число составляют приращение, например [10, 5, 30] или [10, 5 , 8]. Также возможно, что ответ равен 1, когда последовательность убывает.
На первый взгляд мы ничего не нашли, и не нашли хорошего решения для решения проблемы, но на самом деле перед нами очень важный вывод - эта самая длинная последовательность, которая не спускаетсяне обязательно содержит последний элемент.
Может показаться абсурдом, что ответ определенно не включает последний элемент, потому что, если последний элемент очень мал, он, очевидно, не может составить очень длинную последовательность. Но с другой стороны, наши выводы будут полностью извращены. Поскольку ответ не обязательно заканчивается последним элементом, а последовательность должна иметь конец, в настоящее время у нас нет вывода о том, что некий узел может быть концом. Таким образом, мы естественным образом заключаем,Все позиции могут быть в конце ответа.
На самом деле это очень хорошее доказательство, давайте посмотрим на следующую картинку:
В этой последовательности a1, a2 увеличиваются до ai, уменьшаются от ai+1 и
, то, очевидно, [a1.a2,...,ai] есть ответ, то есть ai есть конец ответа. Пока мы меняем значение i, мы можем сделать так, чтобы конец ответа отображался в другом месте. Так что теоретически каждая позиция в массиве может быть концом ответа.
Из этого вывода можно сделать еще один вывод, так как все позиции могут быть концом окончательного ответа,Если мы хотим найти ответ, нам нужно обойти все концы, то есть все позиции. А для определенной позиции обязательно должна быть определена и самая длинная неубывающая подпоследовательность, оканчивающаяся на нее (случаев может быть несколько). Итак, после ряда выводов мы пришли к выводу, чтоТребуются ответы на все позиции, и выберите тот, который является лучшим в целом.
Это очень проницательное и интуитивное понимание, но оно недалеко от ответа, мы можем добавить немного рационального анализа.
рациональный анализ
Давайте разберемся с выводами и идеями прямо сейчас, мы знаем ответ, который нужно решить для каждой позиции, а затем найдем из него общий оптимальный. Предположим, мы хотим узнать ответ в конце i-й позиции, что на самом деле означает, что мы отбрасываем все элементы после i-й позиции. Последовательность, которую мы рассматриваем, оставляет только i и часть перед i.
Давайте посмотрим на картинку ниже:
Мы перечисляем ответы массива длины 5 и перебираем все i, каждый i соответствует ответу массива num[:i].Каждый i можно рассматривать как независимую проблему, все, что нам нужно сделать, это найти ответ, соответствующий каждому i.
Поскольку мы запрашиваем ответ для каждого i, можем ли мы использовать уже полученные ранее результаты для ускорения процесса вычислений? Идея всего динамического программирования, полученная здесь, очень ясна.
Предположим, что мы уже знаем все ответы, меньшие или равные i, теперь мы спрашиваем ответ i+1, что нам делать?
Очень просто, мы перебираем все j меньше или равно i, если
меньше или равно
, тогда объясните
За ним может следовать aj для формирования решения. Если мы используем массив dp для хранения ответов для всех позиций, то мы можем получить следующее уравнение перехода:
После того, как уравнение перехода указано, оно очень просто: мы начинаем с наименьшего i, используем предыдущие результаты для вычисления ответа, соответствующего каждому i, а затем находим наибольшее решение в целом. Давайте посмотрим на код, чтобы увидеть больше деталей:
nums = [65, 158, 170, 299, 300, 155, 207, 389]
if __name__ == "__main__":
n = len(nums)
dp = [1 for _ in range(n)]
for i in range(1, n):
# 遍历i之前的所有已经得出答案的位置
for j in range(i):
# 如果i可以跟在j后面
if nums[i] >= nums[j]:
# 则尝试用j来更新i
dp[i] = max(dp[i], dp[j] + 1)
print(max(dp))
Этот код очень короткий, всего два цикла, и в сочетании с предыдущим описанием его должно быть легко понять. Наш анализ сложности также очень прост.Начиная с двойного цикла, мы, очевидно,
. Мы также можем начать с количества состояний и количества решений, ответом на каждое из наших окончаний является состояние, а число равно n. Для каждого состояния можно проследить каждую позицию поверхности, поэтому наихудшее количество потенциальных решений равно n, поэтому общая сложность равна
.
Хотя мы потратили много пера и чернил, этот алгоритм не сложен, это действительно сложность конкурса средней школы. Но не волнуйтесь, проблема не решена, наша следующая проблема, этот алгоритмЕсть ли место для улучшения?
Передовой
Теперь, когда вопрос задан, ответ, очевидно, да. Если интервьюер спросит вас, можете ли вы улучшить свои навыки во время интервью, если вы ответите «нет», с вас будет снято много баллов. Интервьюер либо считает вас слишком безрассудным, либо считает, что ваш эмоциональный интеллект - цыпленок, поэтому, если вам зададут вопрос во время интервью, вы должны ответить утвердительно.Насчет того, как оптимизировать, вы можете думать медленно, но очень серьезно.
На самом деле есть только два случая оптимизации задач динамического программирования.Либо начните с количества состояний и уменьшите количество избыточных состояний, либо начните с решения, чтобы быстро найти правильное решение. Например, введенная ранее монотонная оптимизация является последней, вообще говоря, число состояний относительно фиксировано, и его трудно уменьшить, и оптимизация часто начинается с принятия решения. Эта проблема не исключение, так как же нам ее оптимизировать?
Если вы хотите оптимизировать, информации перед вами недостаточно.Алгоритмы не изобретаются из воздуха, они часто выводятся. Нам еще нужно больше информации и выводов, для каждой требуемой i+1 позиции мы уже знаем все ответы перед ней. Было бы неплохо, если бы мы могли придумать способ быстро узнать, где именно должен следовать i+1.
Этот метод неожиданный для нас, и мы должны объединить данные. Давайте используем приведенный выше пример в качестве примера, чтобы нарисовать наилучшее решение о переводе для всех позиций:
Кажется, что здесь нечего смотреть, мы случайным образом выбираем элемент, чтобы внимательно его изучить, предположим, что мы выбрали 207. Перечислим элементы и ответы для всех позиций до 207, иСортировать по размеру элемента, вы можете получить такой результат:
Длины 155 и 158 равны 2, очевидно, мы158 можно удалить, осталось только 155. Поскольку 155 Для позиций одинаковой длины нам нужно сохранить только наименьшую.
Соблюдаем приведенную выше последовательность,Кажется, что чем больше число, тем больше длина, а чем больше длина, тем больше число., но так ли это на самом деле? Попробуем изменить значение:
Мы изменили 158 на 358, и кажется, что мы не удовлетворены.Хотя 358 очень большой, его ответ очень маленький. Но когда мы делаем дедупликацию в соответствии с вышеизложенными принципами, мыОстальная часть последовательности все еще увеличивается. Это просто совпадение или правда?
Мы можем попытаться доказать это, предполагая наличие контрпримера. Мы предполагаем, что в массиве есть два числа x и y, оба из которых существуют в массиве ответов после дедупликации. где x
Мы используем следующий рисунок, чтобы проиллюстрировать приведенный выше контрпример.
То есть для той, которую мы получаем после обработкиЭлементы в массиве dp должны быть увеличены, так гдеПозиция каждого элемента фактически представляет соответствующую длину элемента.. Например, на приведенном выше рисунке 2 занимает второе место в массиве, тогда это означает, что ответ, соответствующий числу 2, равен 2.
Процесс обновления массива dp в основном делает две вещи.Во-первых, нужно сделать элементы в массиве dp как можно больше.Мы каждый раз будем вставлять наибольшее число в конце dp. Другое дело, чтобы элементы каждой позиции в массиве dp были как можно меньше. Таким образом, вы можете подготовиться к вставке как можно большего количества элементов.Если предыдущее число особенно велико, то нет возможности передать другие числа позже.
Например, ответы 3 и 9 на картинке выше равны 3, но очевидно, что 3 лучше, чем 9, потому что 3 может соответствовать ответу 3, а это означает, что число, которое появляется справа от 3, пока оно больше 3 может получить по крайней мере длину 4. Мы можем понять, что ответ, соответствующий 3, равен 3,Также можно понять, что минимальное удовлетворяющее число, соответствующее ответу 3, равно 3., вместо 9.
Поскольку элементы в массиве dp упорядочены, мы можемИспользуйте дихотомию, чтобы найти местоположение соответствующего обновления, что гарантирует, что мы сможем найти оптимальное решение за время logN. Тогда общая сложность становится такой, что количество состояний равно n, количество решений равно logN, а окончательная сложность равна
.
Давайте посмотрим на код:
from bisect import bisect_right
nums = [65, 158, 158, 299, 300, 155, 207, 389]
if __name__ == "__main__":
n = len(nums)
dp = [nums[0]]
for i in range(1, n):
if nums[i] >= dp[-1]:
# 由于dp当中元素是递增的
# 所以nums[i] > dp[-1]表示nums[i]是最大的
dp.append(nums[i])
else:
# bisect_right是二分函数，找到dp当中大于nums[i]的位置
pos = bisect_right(dp, nums[i])
dp[pos] = nums[i]
print(len(dp))
Суммировать
На этом вопрос разъяснен, и суть всего вопроса заключается в нашемподдерживает упорядоченный массив, что позволяет найти оптимальное решение для каждого состояния бинарным поиском. Мне стыдно сказать, что я решал эту задачу несколько раз, но я не мог вспомнить решение много раз раньше, и я забуду его через некоторое время, и тогда я нашел трюк. Мы не можем запомнить, как работает алгоритм, поэтому не сможем сделать это в следующий раз, когда столкнемся с вариантом. мыНеобходимо понять причину такой оптимизации, причину и следствие вывода, чтобы у нас была возможность вывести другие задачи.
Поэтому я надеюсь, что каждый сможет понять процесс этого вывода, а не просто остановиться на том, как мы используем дихотомию для оптимизации. Существуют и другие варианты этого вопроса, например, если мы хотим спроситьДля перехвата всех ракет требуется как минимум несколько ракетных комплексов,Что я должен делать? Этот вопрос остается для размышления каждого. Я думаю, если вы сможете понять описанный выше подход, вам не составит труда найти ответ.
На сегодняшней статье все. Если вы чувствуете, что что-то приобрели, пожалуйста, нажмитеПодпишитесь или сделайте ретвитЧто ж, твое маленькое усилие много значит для меня.