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; } }

## Comments

## Post a Comment