DP - Climbing Stairs

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?

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. step 1 + step 1 ( take one step)
2. step 2 ( directly go to second step)

Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
  1. step 1 + step 1 + step 1( take one step)
  2. step 1 + step 2 ( take step 1 and then take 2 steps)
  3. step 2 + step 1 ( take 2 steps and then take 1 step)

Solution using brute force approach
Solution using DP memoization
Solution using DP Bottom-Up approach using tabulation
Solution using DP Bottom-Up approach memory optimized

In this approach, we will compute all possible outcomes recursively, by taking possibilities of 1 step and 2 steps from current step we are in.

We will create a function climbStairsBruteForce that takes n as input argument.
Call climbStairsBruteForce itself with two possible outcomes, i.e. n-1 and n-2, thus reducing number of remaining eteps.
While solving the problem recursively, we can draw two base cases.
- When n becomes 0, that means we are at the last step of stair, then return 1.
- If n becomes less than 0, then return 0, as there will be no way to climb stairs.

import java.util.HashMap; public class ClimbingStairs { /* brute force approach */ static int climbStairsBruteForce(int n) { if(n == 0){ return 1; } if(n < 0) { return 0; } return climbStairsBruteForce(n-1) + climbStairsBruteForce(n-2); } }

Complexity Analysis:

Time complexity: Above code runs in O(2ⁿ) time where n is the input number, this is because we are creating a decision tree with two possibilities at each step.
Space complexity: O(n) as we are making recursive loops n times and this is the memory used by stack.

From the above brute force approach, we can notice that there are some overlapping problems.

For example, let's say n = 5

We start at 1^st step, then we can either take 1 step or 2 steps.
We reach step 3, by taking either 1 step two times from 1^st step, or by taking 2 steps from 1^st step.
Once we are at step 3, number of ways to reach step 5 will be same whether we take 1 step approach or 2 steps approach from 1^st step.
So, this is an overlapping sub problem and the results can be cached.

In this approach of memoization, we are going to cache the sub problem results with key as n and its result into a HashMap.
When the sub problem answer is found in the cache, we simply return that, if not then we call the function recursively and cache it.

import java.util.HashMap; public class ClimbingStairs { /* Using DP memoization*/ static int climbStairsUsingMemoization(int n) { HashMap<Integer, Integer> cache = new HashMap<>(); return climbStairsUsingMemoizationRecursive(n, cache); } static int climbStairsUsingMemoizationRecursive(int n, HashMap<Integer, Integer> cache) { if(n == 0){ return 1; } if(n < 0) { return 0; } if(cache.containsKey(n)) { return cache.get(n); } int result = climbStairsBruteForce(n-1) + climbStairsBruteForce(n-2); cache.put(n, result); return result; } }

Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the input number.
Space complexity: O(n) as we are making recursive loops n times and this is the memory used by stack and cache we are maintaining.

In this approach we will look at solving the problem using Dynamic programming using tabulation caching mechanism.
The time and memory complexity will be same as above solution using memoization, but we can notice a pattern to improve memory complexity to constant in later solution.

Intution behind this solution is, when we are at i^th step, possible ways to reach that steps are possible ways to reach i -1^th step plus possible ways to reach i -2^nd step. This is because, If you take a look at below diagram, to reach step 2, we can either take 1 step from 1^st step or two steps directly.

We will create a temporary array int[] dp = new int[n+1] with n+1 in size, because we are going to cache how many ways to reach 0^th step as well for convinience.
Then, initializedp[0] = 1 and dp[1] = 1, reason we add dp[0] = 0 is for our convinience, to reach step 2, we can take 1 step from 1^st step or 1 step from 0^th step.

dp[i] = dp[i-1] + dp[i-2];

public class ClimbingStairs { /* Using DP tabulation */ static int climbStairsUsingTabulation(int n) { int[] dp = new int[n+1]; dp[0] = 1; dp[1] = 1; for(int i=2; i<=n; i++) { dp[i] = dp[i-1] + dp[i-2]; } return dp[n]; } }

Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the input number.
Space complexity: O(n) since we have a dp array with size n+1.

If we look at above DP solution using tabulation, we can see that we just need previous two values only.
If we are at step i, we only need number of ways to reach i-1^th step and i-2^nd step.

In this approach, we will create two variables prev and current to hold previous values for i-2^nd step and i-1^st steps respectively.
Once we calculte number of ways we can reach current i^th step we are looking at using prev + current, for the next iteration, we will reset prev and current such that new value at current i^th step will become new current and previous current value will become new prev.

public class ClimbingStairs { /* Memory efficient */ static int climbStairsMemoryEfficient(int n) { int prev = 1; // start at step 0 int current = 1; // start at step 1 for(int i=1; i<n; i++) { int temp = current; current = prev+current; prev = temp; } return current; } }

Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the input number.
Space complexity: O(1) since we are only using prev, current and a temp variables.

Above implementations source code can be found at GitHub link for Java code

Contents

Complexity Analysis:

Complexity Analysis:

Complexity Analysis:

Complexity Analysis: