Leetcode Climbing Stairs Problem Solution

In this Leetcode Climbing Stairs Problem Solution You are climbing a staircase. It takes n steps to reach the top.

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

Problem solution in Python.

 def climbStairs(self, n: int, cache = None) -> int:
        if n == 0 : return 1
        if n == 1 : return 1
    
        if cache is None: cache = {}
        if n in cache: return cache[n]
    
        result = self.climbStairs(n-1, cache) + self.climbStairs(n-2, cache)
        cache[n] = result
        return result

Problem solution in Java.

import java.util.*;
class Solution 
{
    Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    
    public int climbStairs(int n) 
    {
        if(n ==1 || n ==2)
            return n;
        
        int result =0;
        
        if(map.containsKey(n-1))
            result += map.get(n-1);
        else
            result += climbStairs(n-1);
        
        if(map.containsKey(n-2))
            result += map.get(n-2);
        else
            result += climbStairs(n-2);
        
        map.put(n, result);        
        return result;
    }
}

Problem solution in C++.

class Solution {
public:
    int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        int a = 1;
        int b = 2;
        int c = 3;    
        for (int i = 3; i <= n; i++) {
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }
};

Problem solution in C.

int climbStairsCore(int n, int *record) {
    if (n == 1) {
        return 1;
    }
    else if (n == 2) {
        return 2;
    }
    else {
        int resultA = *(record + n - 1);
        if (resultA == -1) {
            resultA = climbStairsCore(n - 1, record);
            *(record + n - 1) = resultA;
        }
        
        int resultB = *(record + n - 2);
        if (resultB == -1) {
            resultB = climbStairsCore(n - 2, record);
            *(record + n - 2) = resultB;
        }
        return (resultA + resultB);
    }
}
 
int climbStairs(int n) {
    int *record = malloc(sizeof(int)*n);
    for (int i = 0; i < n; i++) {
        *(record + i) = -1;
    }
    return climbStairsCore(n, record);
}