Difficulty: Easy Link: Day 8: June Leetcode Challenge
You are given an integer array
cost[i] is the cost of
ith step on a staircase. Once you pay the cost, you can either climb one or two steps.
You can either start from the step with index
0, or the step with index
Return the minimum cost to reach the top of the floor.
Input: cost = [10,15,20] Output: 15 Explanation: Cheapest is: start on cost, pay that cost, and go to the top.
Input: cost = [1,100,1,1,1,100,1,1,100,1] Output: 6 Explanation: Cheapest is: start on cost, and only step on 1s, skipping cost.
2 <= cost.length <= 1000
0 <= cost[i] <= 999
We can move either 1 step or 2 step, this is a choice we have to make in order to minimise the effort for reaching the destination. If you carefully look at the examples, you need to always consider the best of past two choices you made at any point. To reach at any point, we would have either jumped 1 step from previous stair or jumped 2 stairs from last 2 rows. We have to always choose the minimum of the costs. Does it look familiar? Which approach does it screams of?
Congratulations if you guessed it just by reading the problem. If you are new to the Dynamic Programming, then probably this is the starer problem you would see on the Leetcode. To solve any DP problem, there are basically two ways to build up the solution. 1. We can start from the lowest sub-problem and reach the final solution by caching the solved results(Tabulation / Bottom Up Approach). 2. We can start from the main problem and recursively break down in two smaller sub problems and saving those small results along the way to avoid re-computation.
We are iterating over the input linearly for building our memoization table. So, both time and space would be bounded by linear
- Time complexity: O(N)
- Space complexity: O(N)