Dynamic Programming: Implementing a solution using memoization

Admin 1
Viewed 57

As the question states, I am trying to solve a leetcode problem. The solutions are available online but, I want to implement my own solution. I have built my logic. Logic is totally fine. However, I am unable to optimize the code as the time limit is exceeding for the large numbers.

Here's my code:

let count = 0;

const climbingStairs = (n, memo = [{stairs: null}]) => {

if(n === memo[n]) {
    count += memo[n].stairs;
}

if(n < 0) return;

if(n === 0) return memo[n].stairs = count++;

memo[n] = climbingStairs(n - 1, memo) + climbingStairs(n - 2, memo); 

return memo[n];
}

climbingStairs(20); //running fine on time
climbingStairs(40); //hangs as the code isn't optimized

console.log(count); //the output for the given number

The code optimization using the memoization object is not working. I have tried multiple ways but still, facing issues. Any help would be appreciated in optimizing the code. Thanks!

memoization dynamic-programming javascript
2 Answers

no need for count value, you can memoize this way:

const climbStairs = (n, memo = []) => {
    if(n <= 2) return n;
    if(memo[n]) {
        return memo[n];
    }
   
    memo[n] = climbStairs(n - 1, memo) + climbStairs(n - 2, memo); 
    return memo[n];
}
user_113744240

Actually, you do not store a value, but NaN to the array.

You need to return zero to get a numerical value for adding.

Further more, you assign in each call a new value, even if you already have this value in the array.

A good idea is to use only same types (object vs number) in the array and not mixed types, because you need a differen hndling for each type.

const climbingStairs = (n, memo = [1]) => {
    if (n < 0) return 0;
    return memo[n] ??= climbingStairs(n - 1, memo) + climbingStairs(n - 2, memo);
}

console.log(climbingStairs(5));
console.log(climbingStairs(20));
console.log(climbingStairs(40));

user_14476750
Related