70. Climbing Stairs¶

// Memoization array to cache results
int[] memo;

// Recursive helper function to count ways to climb to step n
int countWays(int step) {
    // Base case: only 1 way to reach the first step
    if (step == 1) return 1;

    // Base case: two ways to reach the second step (1+1 or 2)
    if (step == 2) return 2;

    // Return cached result if already computed
    if (memo[step] != -1) return memo[step];

    // Compute the result recursively and store it
    memo[step] = countWays(step - 1) + countWays(step - 2);

    return memo[step];
}

public int climbStairs(int n) {
    // Initialize memo array with -1 to indicate uncomputed values
    memo = new int[46];
    Arrays.fill(memo, -1);

    // Compute and return the number of ways to climb n stairs
    return countWays(n);
}