В этом посте я расскажу о решении проблемы с 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. сделай 1 шаг, а затем сделай 2 шага
  3. сделай 2 шага, а затем сделай 1 шаг

Допустим, введено 2, т.е. вам нужно подняться всего на 2 ступеньки. Есть 2 способа сделать это.

  1. делать 1 шаг за раз
  2. сделать 2 шага за один раз

Допустим, введено 1, то есть вам нужно подняться на 1 ступеньку. Есть только один способ сделать это.

  1. сделать 1 шаг

Вы видите какой-нибудь паттерн в приведенном выше примере? Количество способов, которыми вы можете подняться на n шагов, на самом деле является суммой количества способов, которыми вы можете подняться на n -1 шагов, и количества способов, которыми вы можете подняться. может подняться на n-2 ступенек. Это наш алгоритм решения этой проблемы. Посмотрим, как это выглядит -

  1. Создайте массив steps с размером = n, чтобы хранить количество путей, по которым вы можете пройти каждый шаг в массиве.
  2. В качестве базового случая, если n ≤ 2, мы возвращаем n по очевидным причинам.
  3. Инициализируйте steps[0] = 1 и steps[1] = 2, как мы видели в примере выше.
  4. Начинаем с третьего шага до тех пор, пока не дойдем до n и рассчитаем количество способов для каждого шага
  5. В конце мы возвращаем 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