Как решить проблему лестницы на JavaScript с помощью мемоизации

Я хочу написать небольшое продолжение предыдущей заметки о том, как решить проблему лестницы с помощью 5 строк JavaScript.

Это очень элегантное решение печально известной проблемы лестницы, * однако, как заметил один из комментаторов, оно ужасно неэффективно, порядка O(3^n).😖.

Вот это да! И что теперь?

Есть классный трюк с забавным названием для решения этой проблемы: Memoization. Да, я тоже не совсем уверен, как это произносится! 😂

Вот как выглядит проблема с лестницей в мемоизации…

function stairSteps(N) {

  // store repeat values in memo to prevent repeat computations
  const memo = [];

  function stepsM(N) {

    if (N === 0) return 1;
    else if (N < 0) return 0;

    if (memo[N] !== undefined) return memo[N];
    else {
      memo[N] = stepsM(N - 1) + stepsM(N - 2) + stepsM(N - 3);
      return memo[N];
    }
  }

  return stepsM(N);
}

Идея проста: массив memo просто хранит значения, которые могут повторяться, чтобы вы могли ссылаться на них позже вместо того, чтобы вычислять их снова — что является СУПЕР дорогим в случае рекурсии.

Например…

Если вы знаете значение stepsM(N-3), которое вычисляется в первом раунде stepsM(N), вам НЕ нужно вычислять его значение снова, когда оно будет вызвано позже stepsM(N-1) или stepsM(N-2).

Довольно аккуратно, да?

Если вам понравилась эта статья, пожалуйста, загляните в мой блог
Indepth JavaScript для более глубокого
контента. 🤓