DEV Community

Lizandro J. Ramírez
Lizandro J. Ramírez

Posted on

1

O(n*m) staircase with N steps

Alt Text

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

You can check

code by @difo23

Image of Timescale

🚀 pgai Vectorizer: SQLAlchemy and LiteLLM Make Vector Search Simple

We built pgai Vectorizer to simplify embedding management for AI applications—without needing a separate database or complex infrastructure. Since launch, developers have created over 3,000 vectorizers on Timescale Cloud, with many more self-hosted.

Read more →

Top comments (0)

Billboard image

Create up to 10 Postgres Databases on Neon's free plan.

If you're starting a new project, Neon has got your databases covered. No credit cards. No trials. No getting in your way.

Try Neon for Free →

AWS GenAI Live!

GenAI LIVE! is a dynamic live-streamed show exploring how AWS and our partners are helping organizations unlock real value with generative AI.

Tune in to the full event

DEV is partnering to bring live events to the community. Join us or dismiss this billboard if you're not interested. ❤️