O(n*m) staircase with N steps

Lizandro J. Ramírez ・2 min read

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;

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

Posted on by:

Lizandro J. Ramírez

I’m an enthusiast's software development