746. Min Cost Climbing Stairs

Problem¶

You are given an integer array cost where 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 1.

Return the minimum cost to reach the top of the floor.

Example 1:

Input: cost = [10,15,20]
Output: 15
Explanation: You will start at index 1.

• Pay 15 and climb two steps to reach the top.
  The total cost is 15.

Example 2:

Input: cost = [1,100,1,1,1,100,1,1,100,1]
Output: 6
Explanation: You will start at index 0.

• Pay 1 and climb two steps to reach index 2.
• Pay 1 and climb two steps to reach index 4.
• Pay 1 and climb two steps to reach index 6.
• Pay 1 and climb one step to reach index 7.
• Pay 1 and climb two steps to reach index 9.
• Pay 1 and climb one step to reach the top.
  The total cost is 6.

Constraints:

• 2 <= cost.length <= 1000
• 0 <= cost[i] <= 999

Solve¶

White board¶

Quick glance on the problem give me a fell of “this is a Dynamic programming”

Now I need to find a Recursive formulation:

• I first thought on that we storing the answer of all child problem in the memory

First approach: Storing the answer directly¶

cost = [10,15,20]

And we try to create
res  = [10,10,15]

When reading the problem description, and needed answer, I set up the baseline answer with

res[0] := cost[0]
res[1] := min(cost[1], cost[0])

Now how to get 15 in res[2], I try

res[2] = min(res[1], c + res[0])

This is base on observation that:

• To go to index 2 i first need to go to index 0 or 1
• If i get to index 2, … < This is where I found out a really trouble some of my first approarch >

By some quick analyse, I found out a big hole in my first attempt:

• When we get to res[0] or res[1], it unsure we needed to buy index 0 or index 1 or not, making it not possible to know if we need to buy either of them to get to res[2]
• This mean I need more stage value on how can I get to res[0] or res[1]

By more deeply thought, I believe I got it wrong on my res value which need to be res = [0,0,15] and not res = [10,10,15].

This could still be a possible approach.

Second approach: Storing staged value only.¶

Using the first approach end analysis, I quick change to a staged result only. I attempt on storing value that is smallest total that I can jump to and buy the current index spot.

cost  = [10, 15, 20]

total = [10, 15, 30]

Base value

total[0] = cost[0]
total[1] = cost[1]

Formula

total[2] = cost[2] + min(total[0], total[1])

• We always buy the current spot, so cost[2] need to be added
• To jump to index 2, we at least need to stand at index 0 or index 1 step. So min(total[0], total[1]) will set us up at the right position to jump to step 2 at minimal total price.

Our answer, will either be at the last step or previous of last step of the staircase.

res = min(total[last_step], total[last_step-1])

Quick implementation in python

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        total = []
        for c in cost:
            if len(total) == 0:
                total.append(c)
                continue
            if len(total) == 1:
                total.append(c)
                continue
            total.append(c + min(total[-2], total[-1]))
        print(total)
        return min(total[-1], total[-2])

Testing the code¶

Trying this code on some input result:

Example 1:

cost  = [10, 15, 20]
total = [10, 15, 30]
res   = 15

Example 2:

cost  = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
total = [1, 100, 2, 3, 3, 103, 4, 5, 104, 6]
res   = 6

Hand create test case:

cost = [10,15,20,5 , 2, 2, 3, 7, 8, 9, 7, 8, 9,21, 3,574, 9, 2,321, 8, 9]
total= [10,15,30,20,22,22,25,29,33,38,40,46,49,67,52,626,61,63,382,71,80]
res  = 71

It seem that it do exactly what I describing approach.

I submit it directly into Leetcode which return

Runtime: 57 ms Beats: 79.52%
Memory: 16.4 MB Beats: 78.37%

Implementation: DP - Storing staged value¶

go
O(n)

• Knowing the answer, i implementing it in go language for better performance, also using only 2 variable as we only need two most recently used value of the total array in our quick draft python code

func min(a int,b int) int {
    if a < b {
        return a
    }
    return b
}

func minCostClimbingStairs(cost []int) int {
    a := cost[0]
    b := cost[1]
    for i := 2; i < len(cost); i ++ {
        if i%2 == 0 {
            a = cost[i] + min(a,b)
        } else {
            b = cost[i] + min(a,b)
        }
    }

    return min(a,b)
}

The final result is:

• Runtime 6ms (Beats 14.00% of users with Go)
• Memory 2.84MB (Beats 79.74%of users with Go)