@dc65k

Как правильно решить задачу, используя формулу комбинаторики?

Все привет. Есть задача с LeetCodeпо комбинаторике:
70. Climbing Stairs
You are climbing a staircase. It takes n steps to reach the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Example 1:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
Example 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

Одно из возможных решений:
const climbStairs = (n) => {

    if (n <= 3) {
        return n;
    }

    let ways = [0, 1, 2, 3];

    for (let i = 4; i <= n; i++) {
        ways.push(ways[i - 1] + ways[i - 2]);
    }

    return ways.pop();
}

Но я бы хотел решить её с помощью классической формулы по комбинаторике.
Напишу ход своих мыслей, сначала нужно определиться с формулой:
Размещение
Порядок элементов важен, повторов нет.
https://ru.wikipedia.org/wiki/Размещение

Подскажите, где ошибка?

const factorial = (n) => {

    if (n) {
        return n * factorial(n - 1);
    }

    return 1;
}

const s = (n, k) => factorial(n) / factorial(n - k);

console.log(s(4, 2)); // 12
/*
    Размещение
    Порядок элементов важен, повторов нет.

    n - всего четыре ступени
    k - два варианта подъёма, либо один шаг, либо два

    [1, 1, 2]
    [2, 2]
    [1, 2, 1]
    [2, 1, 1]
    [1, 1, 1, 1]

 */
  • Вопрос задан
  • 143 просмотра
Решения вопроса 1
wataru
@wataru Куратор тега Математика
Разработчик на С++, экс-олимпиадник.
Размещение тут не лучшая идея, потому что придется перебирать, сколько же двоек будет в пути.

Тут вообще-то ответ - числа фиббоначи. Подумайте, почему.
Ответ написан
Комментировать
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы