В этом посте я расскажу о решении проблемы с leetcode - Восхождение по лестнице.
Проблема:
Вы поднимаетесь по лестнице. Чтобы достичь вершины, нужно сделать 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
Ограничения:
1 <= n <= 45
Решение:
Это одна из классических задач на собеседовании, которую до сих пор мне задавали как минимум 2–3 раза. Давайте рассмотрим небольшой пример, прежде чем углубляться в алгоритм.
Допустим, введено 3, т.е. вам нужно подняться всего на 3 ступени. Есть 3 способа сделать это.
- делать 1 шаг за раз
- сделай 1 шаг, а затем сделай 2 шага
- сделай 2 шага, а затем сделай 1 шаг
Допустим, введено 2, т.е. вам нужно подняться всего на 2 ступеньки. Есть 2 способа сделать это.
- делать 1 шаг за раз
- сделать 2 шага за один раз
Допустим, введено 1, то есть вам нужно подняться на 1 ступеньку. Есть только один способ сделать это.
- сделать 1 шаг
Вы видите какой-нибудь паттерн в приведенном выше примере? Количество способов, которыми вы можете подняться на n шагов, на самом деле является суммой количества способов, которыми вы можете подняться на n -1 шагов, и количества способов, которыми вы можете подняться. может подняться на n-2 ступенек. Это наш алгоритм решения этой проблемы. Посмотрим, как это выглядит -
- Создайте массив
steps
с размером = n, чтобы хранить количество путей, по которым вы можете пройти каждый шаг в массиве. - В качестве базового случая, если n ≤ 2, мы возвращаем n по очевидным причинам.
- Инициализируйте
steps[0] = 1
иsteps[1] = 2
, как мы видели в примере выше. - Начинаем с третьего шага до тех пор, пока не дойдем до n и рассчитаем количество способов для каждого шага
- В конце мы возвращаем
steps[n — 1]
в качестве окончательного результата.
class Solution { public int climbStairs(int n) { int[] steps = new int[n]; if (n <= 2) { return n; } steps[0] = 1; steps[1] = 2; for (int i = 2; i < n; i++) { steps[i] = steps[i - 1] + steps[i - 2]; } return steps[n - 1]; } }
Надеюсь, вам понравилось решать эту проблему, и решение помогает! Удачного кодирования! 🙂
Если вы думаете, что решение можно улучшить или что-то упускает, не стесняйтесь комментировать. Всегда есть возможности для улучшения.
Найдите решения для проблем с leetcode здесь - https://github.com/rishikeshdhokare/leetcode-problems