Ways to climb a stair case

You are climbing a stair case. Each time you can either make 1 step or 2 steps or 3 steps. The staircase has N steps. In how many distinct ways can you climb the staircase ?

Approach (Brute force)

This is a classic Fibonacci type question that can be solved with a simple recursion that sum the results of the previous 3 iterations. The problem is that the runtime will be exponential O(3^N) – since we are calling the recursion 3 times with N depth in each iteration.

Approach (Recursion with memorization)

Since in many cases we are calling the recursion multiple times with the same N, we can store the result in memory and re-use it. This will result in a linier runtime 0(N)

Approach (Iterations)

Instead of using a recursion, we can iterate N times, adding the last 3 results to the final result each time.

Tests

public class PossibleStepsCalculatorTest {

    private static final Approach APPROACH = Approach.Brute;

    @Test
    public void calcPossibleWays_baseCases() throws Exception {
        WaysToClimbCalculator calculator = createCalculator();
        int possibleWays = calculator.calcPossibleWays(2);
        assertEquals(2, possibleWays);

        possibleWays = calculator.calcPossibleWays(1);
        assertEquals(1, possibleWays);

        possibleWays = calculator.calcPossibleWays(0);
        assertEquals(0, possibleWays);
    }

    @Test
    public void calcPossibleWays_smallInput() throws Exception {
        WaysToClimbCalculator calculator = createCalculator();

        int possibleWays = calculator.calcPossibleWays(4);
        assertEquals(6, possibleWays);

        possibleWays = calculator.calcPossibleWays(5);
        assertEquals(11, possibleWays);
    }

    private WaysToClimbCalculator createCalculator() {
        if (APPROACH == Approach.Brute) {
            return new WaysToClimbCalculatorBruteForce();
        } else if (APPROACH == Approach.Memo) {
            return new WaysToClimbCalculatorMemo();
        }
        return new WaysToClimbCalculatorIterative();
    }

    enum Approach {
        Brute,
        Memo,
        Iterative
    }
}

Solution (Brute force)

public class WaysToClimbCalculatorBruteForce implements WaysToClimbCalculator{

    @Override
    public int calcPossibleWays(int numberOfSteps){
        return calcPossibleWaysRecursive(numberOfSteps);
    }

    private static int calcPossibleWaysRecursive(int stepIndex) {
        // Base case
        if (stepIndex <= 2){
            return stepIndex;
        }

        return calcPossibleWaysRecursive(stepIndex - 1) +
                calcPossibleWaysRecursive(stepIndex - 2) +
                calcPossibleWaysRecursive(stepIndex - 3);
    }
}

Solution (Recursion with memorization)

public class WaysToClimbCalculatorMemo implements WaysToClimbCalculator {
    @Override
    public int calcPossibleWays(int numberOfSteps){
        return calcPossibleWaysRecursive(numberOfSteps, new int[numberOfSteps+1]);
    }

    private static int calcPossibleWaysRecursive(int stepIndex, int[] memo) {
        // Base case
        if (stepIndex <= 2){
            return stepIndex;
        }

        if (memo[stepIndex] == 0)
        {
            memo[stepIndex] = calcPossibleWaysRecursive(stepIndex - 1, memo) +
                    calcPossibleWaysRecursive(stepIndex - 2, memo) +
                    calcPossibleWaysRecursive(stepIndex - 3, memo);
        }

        return memo[stepIndex];
    }
}

Solution (Iterations)

public class WaysToClimbCalculatorIterative implements WaysToClimbCalculator {
    @Override
    public int calcPossibleWays(int numberOfSteps) {
        if (numberOfSteps <= 2){
            return numberOfSteps;
        }

        int step0 = 0;
        int step1 = 1;
        int step2 = 2;

        int result = 0;

        for (int i = 2; i < numberOfSteps; i++) {
            result = (step0 + step1 + step2);
            step0 = step1;
            step1 = step2;
            step2 = result;
        }

        return result;
    }
}