подниматься по лестнице

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

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

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

Примечание. Данное n является положительным целым числом.

Пример 1:

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶

Пример 2:

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

источник:LeetCode

идеи

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

Давайте поговорим об идее этого вопроса: если вы переходите к N-му шагу, последним шагом может быть только 1-й или 2-й шаг, поэтому все способы достижения N-го шага равны N-1 и N- 2. Сумма всех способов заказа.

Преобразование в формулу:f(N)=f(N-1)+f(N-2),f(N)означает количество всех путей к N шагам

Известный:f(1)=1а такжеf(2)=2, код выше

var climbStairs = function (n) {
  if (n === 1) {
    return 1;
  }
  if (n === 2) {
    return 2;
  }
  return climbStairs(n - 1) + climbStairs(n - 2);
};

В тесте время ожидания результата истекло при расчете 45-го порядка, и нам нужно подумать, как оптимизировать следующий шаг.

оптимизация

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

С вышеуказанного рисунка мы можем видеть это,f(45) = f(43)+f(44), который затем может продолжать разлагаться:

f(45) = f(43) + f(44);
f(45) = f(41) + f(42) + f(42) + f(43);
// .....
// .....
// .....
// 最后分解到了已知值，即：
f(1) = 1;
f(2) = 2;

На протяжении всего процесса декомпозиции мы обнаружим, что на самом деле есть некоторые повторяющиеся значения, такие как приведенное вышеf(42)решить дважды иf(42)а такжеf(43)Будет продолжать выделять повторяющиеся значения.

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

let dp = new Map();
dp.set(1, 1).set(2, 2);

var climbStairs = function (n) {
  if (dp.has(n)) {
    return dp.get(n);
  }
  let result = climbStairs(n - 1) + climbStairs(n - 2);
  dp.set(n, result);
  return result;
};

Результат после отправки:

• 45/45 cases passed (92 ms)
• Your runtime beats 9.54 % of javascript submissions
• Your memory usage beats 42.58 % of javascript submissions (37.5 MB)

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

продолжать оптимизировать

Мы обнаружили, что после решенияf(45)После этого dp записывает изf(1)прибытьf(45)Все значения , на самом деле мы хотим толькоf(45)ценность .

Давайте передумаемf(45)процесс, разложенный наf(3), а затем запроситьf(4)......доf(45), код выше:

var climbStairs = function (n) {
  if (n === 1 || n === 2) {
    return n;
  }
  // 前一个值
  let pre = 2;
  // 前一个的前一个的值
  let beforePre = 1;
  // 中间变量
  let temp = null;
  for (let index = 3; index <= n; index++) {
    temp = pre;
    pre = pre + beforePre;
    beforePre = temp;
  }
  return pre;
};

Отправьте, чтобы увидеть результаты:

• 45/45 cases passed (76 ms)
• Your runtime beats 42.21 % of javascript submissions
• Your memory usage beats 79.72 % of javascript submissions (37.4 MB)

Это хорошо, в приведенном выше методе используются только 3 переменные, изf(3)до f(45), временная сложность и пространственная сложность очень низки.

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

Интересный алгоритм "Открыть замок вертушки"

Интересный алгоритм "Лучшее время для покупки и продажи акций"