Привет, форкс! В этом блоге я расскажу о самой часто задаваемой задаче в интервью, а именно о восхождении по лестнице.

Вопрос:

Вы поднимаетесь по лестнице. Чтобы добраться до вершины, нужно n шага. Каждый раз вы можете подняться по 1 или 2 ступеням. Какими разными способами вы можете подняться на вершину?

Пример 1:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Пример 2:

Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

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



Подъем по лестнице - LeetCode
Повысьте свои навыки программирования и быстро получите работу. Это лучшее место, чтобы расширить свои знания и подготовиться… leetcode.com



Идея решения. Есть n шагов, вы можете делать либо один шаг за раз, либо два шага вправо. Если вы создадите отношение повторения для этого вопроса, это будет

T(n) = T(n-1) + T(n-2)

T(2) = T(1) + T(0) = 1 + 0 = 1

Базовым случаем было бы if (n == 1 || n == 0), тогда ни один из способов не был бы 1, а другой случай был бы, если (n ‹0) ни один из способов не был бы равен нулю.

Давайте решим этот вопрос с помощью базового рекурсивного решения.

Здесь, если вы четко видите, требуется O (2 ^ n) времени, чтобы рассчитать количество способов подняться по лестнице.

Давайте применим рекурсивный DP, чтобы оптимизировать это решение до O (n).

Здесь выше я также добавил решение для итеративного DP. В DP нам просто нужно проверить, сколько переменных являются динамическими / изменяющимися. Здесь мы ясно видим одну переменную, то есть n является динамическим по всему коду. Поэтому нам нужно взять одномерный массив для хранения результатов достижения каждого шага.

Как мы уже знаем, для достижения шага 0 и 1 есть только один способ, так что

mem [0] = 1, mem [1] = 1

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

mem [2] = mem [2–1] + mem [2–2] = mem [1] + mem [0] = 1 + 1 = 2 способа.

Таким образом, мы можем перебрать n элементов, и в конечном итоге ответом будет mem [n].

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

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