LeetCode #70 Climbing Stairs, How to speed up my solution?

Question

I have a solution to this problem on LeetCode #70 Climbing stairs, My solution is not passing, due to it being slow...

I have added a trampoline utilizing thunks and I've added Memoization, what else can I add to speed this up to actually pass the time requirement for this problem my code is below, and thanks in advance.

The description on LeetCode:

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

Example 1:

Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps


Example 2:

Input: 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

Link to problem on LeetCode: https://leetcode.com/problems/climbing-stairs/

let cache = {};

const sumStairSteps = arr => arr.reduce((acc, cur) => acc + cur, 0);

const thunk = (fn, ...args) => {
    return () => fn(...args);
}

const climbStairsHelper2 = fn => {

    let thunk = fn();

    while (typeof thunk === "function") {
        thunk = thunk();
    }

    return thunk;
};

const climbStairs2 = (newStairSequence, ladderCount) => {
    const sum = sumStairSteps(newStairSequence);

    if (sum === ladderCount) {  cache[ladderCount] = cache[ladderCount] + 1; }


    if (1 + sum <= ladderCount) {
        climbStairsHelper2(thunk(climbStairs2, [ ...newStairSequence, 1 ], ladderCount));
    }

    if (2 + sum <= ladderCount) {
         climbStairsHelper2(thunk(climbStairs2, [ ...newStairSequence, 2 ], ladderCount));
    }
};

const climbStairs = n => {
        if (n in cache) return cache[n];
        cache[n] = 0;
        climbStairs2([], n);
        console.log(cache[n]);
        return cache[n];
};

Answer 1

I don't quite follow the approach you're using here. The problem is actually pretty straightforward: code the naive recursive solution, then memoize the results. That is, if you visit a stair in the cache, return it, otherwise compute it. Runtime is linear.

const climbStairs = (goal, curr=0, memo={}) => {
  if (goal < curr) {
    return 0;
  }
  else if (goal === curr) {
    return 1;
  }
  else if (curr in memo) {
    return memo[curr];
  }
  
  return memo[curr] = climbStairs(goal, curr + 1, memo) +
                      climbStairs(goal, curr + 2, memo);
};

console.log(climbStairs(50));

Answer 2

Ok, so you want the solution to be more optimised.

The solution which is currently being discussed by you has linear runtime i.e. O(N) and is accepted on LeetCode. For now let's not talk about the space complexity.

This problem and a category of these problems can be solved by a method called Matrix Exponentiation which has logarithmic runtime i.e. O(Log N)

Matrix Exponentiation is very well described at this link

https://discuss.codechef.com/t/building-up-the-recurrence-matrix-to-compute-recurrences-in-o-logn-time/570

Answer 3

You can solve this problem by using Fibonnacci Series

Here is my code that passed all test cases

    public int ClimbStairs(int n) 
    {
        
            //FIBONACCI SOLUTION

            // base cases
            if (n <= 0) return 0;
            if (n == 1) return 1;
            if (n == 2) return 2;

            int one = 2;
            int two = 1;
            int temp = 0;

            for (int i = 2; i < n; i++)
            {
                temp = one + two;
                two = one;
                one = temp;
            }
            return temp;
        
    }