## DEV Community is a community of 724,337 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Lizandro J. Ramírez

Posted on

# O(n*m) staircase with N steps # 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 = 1;

for (let i = 0; i <= n; ++i) {

let temp = 0;

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))
``````

You can check

code by @difo23