"Cracking the coding interview", 8.1.2

cracking-the-coding-interview-8-1-2.js

/**
 * Находит количество всех возможных вариантов
 * как можно добраться до n-й ступени по лестнице,
 * если можно пройти 1, 2 или 3 ступени за один шаг.
 *
 * Используется кеш, ссылка на который передается вторым аргументом
 * через все рекурсивные вызовы функции.
 *
 * @param {number} n
 * @param {array<number>} cache
 * @returns {number}
 */
function countWays(n, cache = []) {
  if (n < 0) {
    return 0;
  }
  if (n === 0) {
    return 1;
  }
  if (cache[n]) {
    return cache[n];
  }
  cache[n] = countWays(n - 1, cache) + countWays(n - 2, cache) + countWays(n - 3, cache);
  return cache[n];
}