In this approach, we will compute all possible outcomes recursively, first by stating at index 0 and take minimum cost to reach top of the floor, then start at index 1 and take minimum cost to reach top of the floor. Finally take minimum between these two outcomes.

• We will create a function bruteForceApproach that takes cost array as input argument.
• Create another helper function bruteForceApproachRec that take cost and start variable to indicate the start index of the sub array we should be considering.
  • Call this function recursively, by moving start to +1 and +2 indexes as the problem states, we can either takes 1 step or steps. Finally take the minimum of these two possibilities, add it to current node and return to its parent node.
  • Base case will be, when it reaches end of array or goes out of bounds as we are trying with +1 and +2 index from every start index.
  
• Call the above created helper function from index 0 and 1 as the problem states, we can either start at index 0 or index 1, and take the minimum values from these results.

Complexity Analysis:

Time complexity: Above code runs in O(2ⁿ) time where n is the length of cost input array, 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 cost = [4, 1, 8, 3]

• If we draw a decision tree with possible paths, it looks like below diagram.
• If you notice above diagram, highlighted paths are overlapping sub problems.
• So, in this approach, we will be caching sub problem result into a HashMap with start index as key and its result as value. When a sub problem is repeated and found in cache, we will return it, otherwise we will the function recursively and cache its result.

Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the length of cost input array.
Space complexity: O(n) for the cache we are maintaining and stack for recursive calls.

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 step with minimum cost will be Min(cost at index i-1, cost at i-2), when we store the result back into cache, we will add cost at current index, so that it represents the cost to come to that index plus cost we should pay to take next step from here.

Base cases for this solution will be dp[0] = cost[0] and dp[1] = cost[1], this is because as the problem states we can either starts at index 0 or 1, if we start at 0^th index, minimum cost will be cost[0], similarly if we start at 1^st index, minimum cost will be cost[1].

Finally, take the minimum stored at last two indexes of the dp array, this will give us the minimum whether we start at index 0 or 1, and take either 1 or 2 steps from those last two indexes.

Complexity Analysis:

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

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, to calculate minimum we only need minimum cost at 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 calculate minimum cost possible at current indexm we will assign that to current and copy previous current to prev for next iteration.

Complexity Analysis:

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