Solution:
Let’s First understand the question:
This question is asking us to find out the possible number of ways one can climb to the top of a staircase while taking either 1 step or 2 steps. What this means is that at each step one has two options, either to take 1 step or 2 steps until they reach to the top.
Let’s look at some examples to help us better understand the question:
Example 1: n = 1
The total number of ways you can get at the top is one.
a. 1 step
Example 2: n = 2
In a case where you have a staircase with 2 steps, there are two number of ways to reach to the top.
a. 1 step + 1 step
b. 2 steps
Example 3: n = 4
There are 5 ways to get to the top.
a. 1 step + 1 step + 1 step + 1 step + 1 step
b. 1 step + 1 step + 2 steps
c. 1 step + 2 step + 1 step
d. 2 step + 1 step + 1 step
e. 2 step + 2 steps
Solution — Java
Condition: n = 4
n = targetStair
0 = currentStair
We will solve this problem using dynamic programming approach which is a technique for solving complex problems by breaking them down into smaller, simpler subproblems and solving them in a recursive manner. There are two main approaches to dynamic programming: top-down and bottom-up.
For this case we are going to use top-down approach.
Top-down approach is simply memoization, where we start by breaking down the problem into subproblem and then store the results in cache so that we do not have to recompute the same subproblem again.
let’s say you are currently standing at staircase 0, which will be your current stair.
At this stair you have two options,
a. Take oneStep = currentStair + 1
b. Take twoSteps = currentStair + 2
Base Cases
§ If current stair is equal to target stair return 1 (As we have found 1 way to reach to the top)
§ If current stair is greater than target stair, then we return 0 (Not possible to reach to the target stair anymore)
Main Logic
At the current stair we have two options, either take oneStep or twoSteps. We then sum up oneStep + twoSteps as this call will return number of ways to reach to the top.
Code:
We create a helper function totalWays to make recursive calls.
Explanation:
After submitting our solution, we get time limit exceeded (TLE), this means that the solution is correct but we need to optimize our code. TLE means the time complexity of your algorithm is too high. To resolve the TLE, we are going to convert our recursive code to dynamic programming approach using a HashMap.
A HashMap stores elements in key/value pairs. Here, keys are unique identifiers used to associate each value on a map. A hashMap is used for caching or memoization to help us avoid recomputing already computed subproblems.
Steps.
· Identify the parameters getting changed in the recursive call, which is currentStair in our problem.
· Declaring a HashMap called memo, and in our case our key and value are both integers.
· Check whether you have already solved that subproblem by checking whether that key is already stored in the map.
· If not solved, resolve the subproblem and store the answer.
Code:
After submitting our code, it successfully passes the test, and we no longer have the TLE error.
Time complexity of our solution is 0(n) due to memoization.
Space complexity is also 0(n) due to the recursive calls used.
Memory usage: 39.74mb