Высотные дома и слишком много лестниц! Ну погоди! Вы когда-нибудь задумывались о количестве способов подняться на вершину? Вероятный ответ - большое НЕТ. Серьезно, подняться по лестнице намного проще, чем тратить свое время и мозг на подсчет количества способов достичь вершины! :П

А вот и хитрость. Что, если в следующий раз вы столкнетесь с тем же вопросом на собеседовании в компании вашей мечты? Ну не волнуйтесь! Я позабочусь о том, чтобы вы умело использовали эту ловушку! ;)

Сегодня мы рассмотрим этот классический вопрос на собеседовании, который не только проверяет вашу способность решать проблемы, но и проверяет, насколько эффективно вы можете ее достичь.

Постановка задачи:

Подсчитайте количество способов добраться до n-й ступеньки, начиная снизу, учитывая, что вы можете делать только 1, 2 или 3 ступеньки за раз.

Прежде чем переходить к решению, попробуйте обдумать вопрос практически и убедитесь, что вы хорошо понимаете проблему.

Надеюсь, вы попробовали это. Я бы порекомендовал вам продолжить чтение этой статьи, чтобы лучше понять проблему.

Подход:

Давайте разберем проблему на более простую, где мы сможем применить наше практическое мышление. Я изменил формулировку проблемы следующим образом:

Подсчет количества способов достичь 3-го уровня, начиная снизу, учитывая, что мы можем сделать 1,2 или 3 шага за раз.

Это означает, что N = 3

{}: представляет собой набор всех возможных способов достижения N

[0, Y, .., N]: от уровня 0 до уровня Y до уровня N (представляет путь в основном)

Чтобы достичь УРОВНЯ 1:

{[0,1]} = ›Возможен только 1 способ, по 1 шагу за раз, чтобы достичь уровня 1 с уровня 0.

Чтобы достичь УРОВНЯ 2:

{[0,1,2], [0,2]} = ›Возможны только 2 способа:

  1. [0,1,2]: делать по одному шагу за раз. Путь: УРОВЕНЬ 0 = ›УРОВЕНЬ 1 =› УРОВЕНЬ 2. Здесь на каждом уровне мы делаем только один шаг.
  2. [0,2]: делать 2 шага за раз. Путь: УРОВЕНЬ 0 = ›УРОВЕНЬ 2. Здесь, на уровне 0, мы сразу делаем два шага и достигли уровня 2.

Чтобы достичь УРОВНЯ 3:

{[0,1,2,3], [0,1,3], [0,2,3], [0,3]} = ›Возможны только 4 способа:

  1. [0,1,2,3]: По одному шагу за раз. Путь: УРОВЕНЬ 0 = ›УРОВЕНЬ 1 =› УРОВЕНЬ 2 = ›УРОВЕНЬ 3. Здесь на каждом уровне мы делаем только один шаг.
  2. [0,1,3]: Путь: УРОВЕНЬ 0 = ›УРОВЕНЬ 1 =› УРОВЕНЬ 3. Здесь, на уровне 0, мы делаем шаг за шагом и достигли уровня 1. После уровня 1 мы сделали 2 шага за раз и достигли уровня 3.
  3. [0,2,3]: Путь: УРОВЕНЬ 0 = ›УРОВЕНЬ 2 =› УРОВЕНЬ 3. Здесь, на уровне 0, мы сразу делаем два шага за раз и достигли уровня 2. После уровня 2 мы сделали еще 1 шаг и достигли уровня 3.
  4. [0,3]: делать 3 шага за раз. Путь: УРОВЕНЬ 0 = ›УРОВЕНЬ 3. Здесь мы сразу делаем 3 шага и переходим с уровня 0 на уровень 3.

Вы нашли какой-нибудь узор? Важно отметить, что у этой проблемы есть частично совпадающие подзадачи. Это означает, что мы знаем, что есть только один способ перейти с уровня на следующий соседний уровень. Чтобы перейти с уровня 0 на уровень 1, количество способов = 1. Теперь, чтобы перейти с уровня 0 на уровень 2, мы можем либо сделать 2 шага за раз и достичь уровня 2, либо мы можем перейти с уровня 0 на уровень 1, а затем с уровня 1 на уровень 2. Здесь обратите внимание, что мы уже известно количество способов перейти с уровня 0 на уровень 1, то есть 1.

Лучшая визуализация вышеуказанной проблемы

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

{}: набор всех возможных способов достижения N

[X, Y, .., 0]: расстояние от X до расстояния Y до расстояния 0 (в основном представляет путь)

Начнем снова:

  1. для N = 1: 1 способ = ›{[1,0]}
  2. для N = 2: 2 способа = ›{[2,1,0], [2,0]}
  3. для N = 3: 4 способа = ›{[3,2,1,0], [3,2,0], [3,1,0], [3,0]}
  4. для N = 4: 7 способов = ›{[4,3,2,1,0], [4,3,2,0], [4,3,1,0], [ 4,3,0], [4,2,1,0], [4, 2,0], [4,1,0]}

Теперь я уверен, что вы сможете найти образец.

Для N = 4

Для N = 3 мы начинаем с расстояния 3. Мы можем сделать 1, 2 или 3 шага.

Делая по одному шагу из 3, мы достигли 2. Мы уже знаем количество способов достичь расстояния 0 с расстояния 2, т.е. такое же, как N = 2 ( {[2,1,0] , [2,0]} ) и, следовательно, {[3,2,1,0], [3,2,0]} = 2 способа.

Делая 2 шага из 3 за раз, мы достигли 1. Нам уже известно количество способов достичь расстояния 0 с расстояния 1, то есть таких же, как N = 1 ( {[1,0]} ) и, следовательно, {[3,1,0]} = 1 способ.

Сделав 3 шага из 3 за раз, мы достигли расстояния 0. Мы также должны считать этот путь. Поэтому мы включим в наш подход базовый вариант, то есть для достижения расстояния 0 до расстояния 0 существует только один способ.

Для N = 0: количество путей от уровня 0 до уровня 0 равно 1.

Вы можете думать об этом так, как будто вы находитесь на том же уровне, на котором хотели быть, поэтому нет другого пути лучше, чем этот.

Поскольку мы нашли повторяющееся отношение, а это значит, что мы можем думать о рекурсивном решении.

Рекурсивное решение

Давайте сначала построим наш базовый случай:

Для N = (0 или 1) numWays (N) = 1, где numWays - количество способов добраться до N-й ступени.

Если допустимое количество шагов было 1 или 2. Тогда

numWays (0) = 1

numWays (1) = 1

numWays (N) = numWays (N-1) + numWays (N-2)

Это то же самое, что и формула последовательности Фибоначчи.

Эта формула означает, что количество способов перейти с расстояния N на расстояние 0 складывается из:

  1. количество способов перейти с дистанции N-1 на дистанцию ​​0
  2. количество способов перейти с дистанции N-2 на дистанцию ​​0

Но в постановке задачи сказано, что количество шагов, которые можно сделать за один раз, равно 1, 2 или 3 шагам. Следовательно, нам нужно изменить наше рекуррентное отношение.

numWays (0) = 1

numWays (1) = 1

numWays (N) = numWays (N-1) + numWays (N-2) + numWays (N-3)

Но здесь для N = 2:

numWays (2) = numWays (2-1) + numWays (2-2) + numWays (2-3)

numWays (2) = numWays (1) + numWays (0) + numWays (-1)

Нам нужно разобраться с этим случаем, несколькими способами добраться до отрицательной лестницы. Оно должно быть 0. Следовательно, определение рекурсивной функции numWays (N) будет выглядеть так:

если (N ‹0) вернуть 0

if (N == 0 || N == 1) вернуть 1

вернуть numWays (N) = numWays (N-1) + numWays (N-2) + numWays (N-3)

Тестовый забег:

numWays (0) = 1

numWays (1) = 1

numWays (2) = numWays (1) + numWays (0) + numWays (-1) = 1 + 1+ 0 = 2

numWays (3) = numWays (2) + numWays (1) + numWays (0)

= {numWays (1) + numWays (0) + numWays (-1)} + 1 + 1

={1 + 1+ 0}+ 2

=4

Наконец-то мы нашли решение нашей проблемы! Но есть еще одна проблема. Вышеупомянутое решение требует экспоненциального времени. Обратите внимание, есть перекрывающиеся подзадачи, то есть мы снова и снова вычисляем одну и ту же проблему. В случае numWays (3) мы должны снова вычислить numWays (2). Мы можем избавиться от этого, сохранив где-нибудь результат numWays (2), когда он вычисляется в самый первый раз. После этого повторно используйте предварительно вычисленное значение в будущем.

Снижение временной сложности:

Создаем массив numWays [] размером = N + 1. В индексе i массива будет храниться количество способов достижения N-го уровня.

Итак, сначала инициализируем numWays [0] и numWays [1] = 1

int numWays [n + 1] = {0};

numWays [0] = numWays [1] = 1;

Теперь мы начинаем заполнять этот массив снизу вверх, то есть начинаем заполнять этот массив с N = 2, пока не достигнем требуемой лестницы.

Код будет выглядеть примерно так:

для i = от 2 до N (включительно):

/ * внутренний цикл for будет проходить все возможные шаги за раз * /

для j = 1,2,3:

// Здесь предложение if обрабатывает случай количества способов достичь отрицательной лестницы

если (i-j≥0) numWays [i] + = numWays [i-j]

В конце мы возвращаем numWays [n].

Последний подход, который мы обсуждали, известен под очень причудливым названием ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ. Посмотрите, как просто построить DP-решение для известного рекурсивного решения. Здесь мы только что создали область памяти для хранения промежуточных результатов. Это хранилище называется массивом мемоизации, возможно, потому, что оно запоминает! Концепция называется мемоизацией. Мы заполняли массив снизу вверх, пока не достигли желаемого результата. Наконец мы вернули результат. Таким образом, мы сэкономили время на повторные вычисления и решили вопрос за время O (N * k), где N представляет собой N-ю ступеньку, а k - количество возможных ступеней, т.е. в данном случае три.

Ура! Мы очень успешно решили эту проблему!

Решая проблему, помните о нескольких шагах:

  1. Хорошо разбирайтесь в постановке проблемы.
  2. Посмотрите, существует ли рекурсивное решение для того же самого, создав образцы тестовых случаев.
  3. Если да, то создайте рекурсивное решение и его базовые случаи.
  4. После создания решения запустите его на примере тестового примера и проверьте, не выполняется ли несколько вычислений повторно, т.е. проверьте, не перекрываются ли подзадачи. Если он существует, запомните этот повторный расчет в массиве.
  5. Для решения проблемы попробуйте использовать восходящий или нисходящий подход.

Таким образом можно решить любую проблему DP.

Спасибо, что уделили время этой статье. Я надеюсь, что вы сочтете это полезным и даст вам ясное представление о теме.

Если у вас все еще есть какие-либо вопросы, не стесняйтесь отвечать. Если вы сочтете это полезным, поделитесь, пожалуйста, с коллегами. Ваши аплодисменты побуждают меня писать больше таких блогов! :)