Представьте, что вы вор, пытающийся украсть как можно больше золота в районе.
Этот микрорайон состоит из одного ряда домов. Вы знаете, сколько золота находится в каждом доме, поэтому можете заранее спланировать, какие дома вы хотите украсть. Но, чтобы не срабатывать какие-либо сигналы тревоги, вы устанавливаете ограничение, которое не будет воровать из любых двух домов, которые находятся в непосредственной близости друг от друга. Это означает, что вы всегда будете выходить хотя бы из одного дома между любыми двумя, которые вы ограбите.
Проблема грабителя дома популярна на собеседованиях по разработке программного обеспечения, вероятно, из-за всех ее практических приложений (сказал он, надеюсь, саркастически).
Я видел, как многие инженеры постоянно борются с этой проблемой, потому что, что неудивительно, оптимальный подход использует динамическое программирование. И это досадно, поскольку это означает, что многие квалифицированные инженеры, вероятно, отказываются от должности, потому что они не могут решить то, что на самом деле является относительно простой проблемой.
Надеюсь, эта статья поможет прояснить интуицию, лежащую в основе оптимального подхода к этой проблеме, и прольет некоторый свет на более глубокую схему решения проблем, которая здесь присутствует.
Давайте начнем с рассмотрения постановки задачи: входы, выходы, ограничения и т. Д. В отношении любой проблемы всегда полезно уточнить, что все это такое и что они означают.
Ваш вход будет массивом целых чисел, представляющим количество золота в каждом доме.
Результатом будет одно целое число, представляющее максимальное количество золота, которое вы можете украсть у соседей.
Так например:
Когда дело доходит до решения проблем, всегда хорошо начинать с примера, достаточно простого, чтобы мы могли увидеть ответ, но достаточно сложного, чтобы не быть тривиальным. Это будет проверка наших подходов и предоставит ценные данные (наблюдения) о проблеме.
Сразу же мы можем заметить, что пропустили два числа между 3 и 5. Это означает, что оптимальное решение не всегда может заключаться в ограблении ближайшего множества домов, которые мы можем найти. Мы можем захотеть пропустить БОЛЬШЕ одного дома.
Мы также можем начать делать некоторые прогнозы относительно сложности времени / пространства. Часто интервьюеры не дают вам четких ограничений, поскольку это может быть большим намеком. Они просто скажут что-то вроде «делай все, что в твоих силах».
Учитывая, что это массив чисел, и мы производим некое агрегирование информации, максимизируя сумму некоторого подмножества этих чисел, разумным предположением может быть то, что мы сможем решить эту проблему оптимальным образом за линейное время. Это ни в коем случае не является гарантией, но, учитывая, что нам, вероятно, придется сканировать каждый дом, чтобы составить наш план, трудно представить способ сделать это БОЛЕЕ оптимальным, чем линейное время.
Но давайте сначала сосредоточимся на подходе грубой силы, и давайте сделаем это на концептуальном уровне. Я задам вопрос:
Учитывая, что нам нужно украсть из подмножества домов, чтобы найти оптимальное количество золота для кражи, какие подмножества нам нужно проверить?
Ответ:
Итак, что представляет собой правильное сочетание домов? Любая комбинация, которая оставляет хотя бы один дом между любыми двумя ограбленными.
Теперь, когда мы установили, что нам нужно протестировать различные допустимые комбинации домов, эта проблема начинает очень похожа на другую задачу, использующую рекурсию. Вы можете угадать, какой именно?
Сначала это может показаться удивительным, но ТАКОЕ много рекурсивных проблем сводятся к этому шаблону, потому что мы, по сути, пытаемся все возможные комбинации решений.
Вот как это выглядит в нашем предыдущем примере:
После того, как мы создали все допустимые подмножества домов, из которых мы можем украсть, все, что нам нужно сделать, это просуммировать все значения в каждом подмножестве и выбрать тот, который дает наибольшую сумму.
Если вам интересно: «Какого черта мне настроить рекурсию для решения этой проблемы?», Вы можете использовать этот высокоуровневый псевдокод. В основном это объяснение на английском:
Переводим это в псевдокод низкого уровня (смесь английского языка и кода):
Вот как выглядит код в JavaScript с использованием рекурсии вспомогательного метода:
Теперь давайте проанализируем временную сложность этого подхода. Если подумать об этом наивно, проверка всех возможных комбинаций домов, вероятно, может показаться большой работой, особенно когда район большой (много элементов в массиве).
Если вы хоть немного знакомы с понятием, что такое набор мощности (набор всех подмножеств), то вы, вероятно, придете к выводу, что это своего рода экспоненциальное время выполнения.
Чтобы справиться с этим самостоятельно, можно вручную сравнить сколько дополнительной работы вам нужно сделать, ДОБАВИВАЯ 1 ДОПОЛНИТЕЛЬНЫЙ ДОМ В ОКРЕСТНОСТИ. В этом примере это означает выяснить, сколько дополнительных комбинаций создается и которые необходимо протестировать, когда вы добавляете еще 1 дом в район.
Вот как это сделать на простом примере:
Вы можете видеть, что входные данные большего размера по-прежнему проверяют все комбинации, заданные в входных данных меньшего размера, плюс все новые, созданные путем добавления дополнительного числа. Только в этом одном примере мы видим, что добавление 1 дополнительного дома означает 5 дополнительных комбинаций, которые необходимо проверить.
Выполнение этого упражнения вручную отнимает много времени, но очень важно получить более глубокое понимание анализа временных / пространственных сложностей. Мой совет, если вы делаете это без каких-либо ограничений по времени и просто пытаетесь учиться, - это попробовать еще несколько вариантов и посмотреть, как все изменится.
Вы даже можете написать код, чтобы узнать, сколько раз выполняется базовый случай для разных размеров ввода:
Попробуйте запустить этот код. Посмотрите, что он напечатает.
Осторожно, спойлеры:
Но в некотором смысле это не должно стать сюрпризом, если вы действительно посмотрите на оба набора кода бок о бок.
Если вы действительно нанесете числа в таблицу результатов, вы получите что-то вроде этого в логарифмической шкале:
При рассмотрении общей сложности пространства нам необходимо проверить как количество вызовов в стеке вызовов в любой момент времени, так и любое вспомогательное пространство, которое мы используем вне рекурсии:
Большой! У нас есть рабочее решение проблемы домашнего грабителя.
И именно здесь интервьюер попросит вас провести оптимизацию. Итак, давайте вернемся к чертежной доске и сделаем несколько наблюдений:
Интуитивно понятно, что мы тестируем множество нежелательных комбинаций. Причина в том, что мы тестируем множество более мелких комбинаций, которые содержатся в более крупных. Это означает, что есть комбинации, которые строго лучше, чем другие. Это означает, что мы можем начать думать о том, как избавиться от этих меньших комбинаций.
Еще на этом этапе следует обратить внимание на любые ключевые идеи, которые могут раскрыть проблему. Это просто наблюдение или верный вывод об этой проблеме. Мы приходим к этому дедуктивно после сбора данных о проблеме. Если вы думаете о процессе решения проблем как о песочных часах, это будет самым узким моментом:
Так в чем же ключевая идея этой проблемы?
Это простой вывод, но он имеет важные последствия. Из наших предыдущих наблюдений мы пришли к выводу, что мы тестируем множество нежелательных комбинаций. Доказательством его истинности является тот факт, что если мы когда-нибудь оставим большую брешь, то найдется дом с положительным количеством золота, которое мы упускаем из виду.
Помните, что это важная деталь проблемы. Это то, о чем вы захотите спросить интервьюера.
Что касается того, как мы используем инсайты, нам придется вернуться к работе с некоторыми примерами и изменить наш подход. Раньше мы пробовали все возможные комбинации. Что, если вместо этого мы разберем пример и рассмотрим его как последовательность различных входных данных? Затем мы можем отследить, как изменился вывод этой последовательности.
Даже на этом одном примере мы можем сделать важный вывод:
Всегда полезно проверить больше примеров, просто чтобы проверить работоспособность. Есть ли смысл в том, что результат всегда должен расти по мере того, как мы увеличиваем объем наших вложений?
Давайте посмотрим:
Похоже, что шаблон в силе. Обратите внимание на примеры, которые мы пробовали. Это те, у которых есть очевидные решения, которые мы можем проверить.
Итак, что делать дальше?
Давайте перепишем все эти результаты в виде таблицы. Вы заметите, что каждый результат соответствует добавлению дома в район. Вот что это значит:
На этом этапе должно быть довольно ясно, что означают эти таблицы, и у вас должно быть некоторое представление о том, почему этот подход работает. Главный вопрос, который у вас должен возникнуть, - «как нам создать эти таблицы?»
Потому что, если вы можете ответить на этот вопрос, вы эффективно решили проблему. На этом этапе остается лишь написать код и отладить любые незначительные синтаксические ошибки или отдельные ошибки.
Но просто иметь эту таблицу в качестве цели - ОГРОМНЫЙ прогресс. Теперь вы точно знаете, что пытаетесь построить. Изначально проблема начиналась расплывчато и широко, а теперь у нас есть очень четкая цель. Обратите внимание на эту закономерность в будущем, когда будете решать новые проблемы. Вы хотите, чтобы ваши задачи были максимально конкретными.
Итак, давайте сначала создадим одну из этих таблиц вручную и посмотрим, сможем ли мы обнаружить какие-либо закономерности. Помните, что представляет каждый элемент в таблице! Это максимальное количество золота, которое вы можете получить, когда достигнете этой точки поблизости. Об этом важно помнить при ЛЮБОЙ проблеме динамического программирования.
Что касается первого элемента, очевидно, что мы захотим украсть из этого дома. Добавим это в нашу таблицу.
Для второго элемента мы либо оставим первый элемент максимальным, если он больше. В противном случае мы выберем воровство у второго элемента. Все идет нормально.
С третьим элементом все становится немного сложнее. Какие у нас есть варианты?
Что ж, мы можем либо добавить к тому, что мы украли из первого дома, ЛИБО мы можем пропустить этот дом и оставить то, что мы украли из второго дома. Это зависит от того, какое из этих двух значений больше.
Всегда полезно перечислить все варианты, доступные вам в конкретном сценарии. И лучший способ выяснить разные возможности - это просто попробовать разные примеры, как я сделал выше.
Теперь добавим четвертый дом. Что мы должны добавить в нашу таблицу?
Интуитивно мы знаем, что ответ - 8, но как нам прийти к этому числу? Мы добавляем одну из пятерок, но какую?
Чтобы ответить на этот вопрос, давайте добавим еще одно число.
Если мы добавим 4, мы легко увидим, что на выходе должно быть 9. Легко взглянуть на ввод и прийти к такому выводу. Но мы хотим разработать способ надежного обнаружения этого 9.
Если мы посмотрим на нашу таблицу, то увидим, что мы прибавляем стоимость нового дома к максимальным показателям золота 2 обратно. Почему? Потому что это максимальное количество золота, которое мы собрали из исходных данных на две единицы меньше (то есть, с двумя меньшими домами).
По сути, мы спрашиваем здесь: «Следует ли нам добавить этот новый дом и пропустить предыдущий или пропустить этот новый дом и украсть у предыдущего?» И мы делаем это каждый раз, когда добавляем новый дом.
Одна важная деталь, которую следует отметить в этом процессе, заключается в том, что мы просто находим максимальное количество золота, которое можем украсть, учитывая полный набор домов, а не отслеживаем, из каких домов мы украли. Нам пришлось бы изменить наше решение, если бы мы хотели получить эту информацию, но, к счастью, нас не волнует, откуда взялось золото. Всегда не забывайте отвечать на вопрос, который вам задали.
С учетом сказанного, давайте переведем это в псевдокод:
«Для каждого дома в списке либо добавьте его золото к индексу max gold 2, либо оставьте индекс max gold 1».
Если мы посмотрим еще на два примера, мы увидим, что шаблон сохраняется:
В первом примере мы складываем 5 и 8 вместе, потому что эта сумма больше 9.
Во втором примере мы оставляем 13, потому что это больше, чем добавление 1 и 9.
То, что мы возвращаем в конце, надеюсь, довольно очевидно: это просто последний элемент в массиве max_gold.
Вот как вы решаете проблему домашнего грабителя. Будем надеяться, что придумывать кодовое решение на данный момент относительно просто. Я рекомендую вам попробовать свои силы, прежде чем взглянуть на решение ниже.
Должно быть довольно легко увидеть, что временная и пространственная сложность являются линейными, поскольку нам нужно выполнить итерацию по каждому элементу один раз, и для каждого элемента мы храним соответствующее максимальное количество золота, возможное в этой точке массива.
Я призываю вас подумать еще об одной небольшой дополнительной благодарности: как мы можем еще немного оптимизировать это решение? Мы можем сделать одну простую настройку, которая сэкономит нам немного места. Вы можете подумать, как мы можем это сделать?
Вот оптимизированные решения:
Основная идея второго: вам нужно только отслеживать два предыдущих максимума. Все остальное можно выбросить.
Надеюсь, вам понравилось чтение, не стесняйтесь писать мне комментарий, если вы думаете, что я что-то упустил или что-то неясно. Это проблема, которую мы решаем в Outco, чтобы помочь инженерам подготовиться к собеседованию по кодированию, поэтому, если вы хотите узнать больше о нашей 5-недельной программе, посетите наш сайт. У нас есть еженедельные сеансы посетителей и новые группы, начинающиеся каждый месяц.
Удачного кодирования!
