# Description:

`This problem was asked by Amazon.`

There exists a staircase with N steps, and you can climb up either 1 or 2 steps at a time. Given N, write a function that returns the number of unique ways you can climb the staircase. The order of the steps matters.

## Example:

For example, if `N`

is `4`

, then there are `5`

unique ways:

- 1, 1, 1, 1
- 2, 1, 1
- 1, 2, 1
- 1, 1, 2
- 2, 2

### Fibonacci:

`N = [0, 1, 2, 3, 4, 5, 6]`

`Output Ways = [1, 1, 2, 3, 5, 8, 13]`

Fibonacci in the output.

## Extra:

What if, instead of being able to climb 1 or 2 steps at a time, you could climb any number from a set of positive integers X? For example, if `X = [1, 3, 5]`

, you could climb `1`

, `3`

, or `5`

steps at a time.

## Solution in JS:

- O(n * m)
- n --> staircase steps ( N )
- m --> valid climb up steps ( X.length )

```
let staircase = (n, X) => {
// Steps climb up
let setX = new Set(X)
// Positions arrays step staircase
// Included 0
let cache = Array(n + 1).fill(0);
// The position 0 is always 1 way.
cache[0] = 1;
for (let i = 0; i <= n; ++i) {
let temp = 0;
// Valid Steps add
for (let x of X) {
if (i - x > 0) {
temp += cache[i - x]
}
}
//Update cache.
cache[i] += temp;
// position numbers
// is included (1) or not (0)
cache[i] += setX.has(i) ? 1 : 0;
}
// The last position in cache have the
// # of ways.
return cache.pop();
}
```

## Simple Test:

```
// Case 1
let X = [1, 2 ];
let n = 4;
console.log(staircase(n, X))
// Case 2
let X = [1, 3, 5];
let n = 4;
console.log(staircase(n, X))
```

## Discussion (0)