Leetcode 746. Min Cost Climbing Stairs (Python)

Related Topic

Dynamic-Programming.

Description

On a staircase, the i-th step has some non-negative cost cost[i] assigned (0 indexed).

Once you pay the cost, you can either climb one or two steps. You need to find minimum cost to reach the top of the floor, and you can either start from the step with index 0, or the step with index 1.

Sample I/O

Example 1

Input: cost = [10, 15, 20]
Output: 15
Explanation: Cheapest is start on cost[1], pay that cost and go to the top.

Example 2

Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Output: 6
Explanation: Cheapest is start on cost[0], and only step on 1s, skipping cost[3].

Note:

1. cost will have a length in the range [2, 1000].
2. Every cost[i] will be an integer in the range [0, 999].

Methodology

This question solved by Dynamic Programming. It is similar with question70. Climbing Stairs

1. Find the base case (Given [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]):

   1. when there are 2 stairs, we choose the min cost from first two steps
   2. When there are 3 stairs, you can either choose stair 1 or stair 2 to reach stair 3, we want the minimum cost, so we will choose the minimum between(cost[0], cost[1]) which is min(1, 100) = 1 ….

2. Find the pattern:

   When there are 3 stars, you can either choose stair 1 or stair 2 to reach stair 3, we want the minimum cost, so we will choose the minimum between(stair 1, stair 2) which is min(cost[0], cost[1]) = 1 and then add minimum value of previous two steps cost to the current stair value, in this case, the current(cost[2]=cost[2]+min(cost[0], cost[1])=2), the cost list become [1,100,2]. Here the reason why we update current value is for next step cost if you have next step.

3. Answer:

   The answer will be the minimum value of previous two steps, not the current value!

4. Extended Options:

   If minimum cost is from previous 3 steps, we simply need to find the min(cost[-2], cost[-3], cost[-4])

Conditions

The length of stair is at least 2 steps.

Code

def minCostClimbingStairs(self, cost: List[int]) -> int:
        for i in range(2,len(cost)):
            cost[i] += min(cost[i-1],cost[i-2])
        return min(cost[-2],cost[-1])

BigO

We iterate all dp array, it will cost O(n), each value will add up minimum value of last two cost as result, it will cost (1+2), in total will be O(n+2n) and It is O(n)