Все привет. Есть задача с 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]
*/
Простой