Today's LeetCode's challenge 2023/10/13

This write-up refers to LeetCode's daily challenge 746. Min Cost Climbing Stairs

Even though this challenge is labeled as easy, I couldn't solve it by myself because I still need to improve my dynamic programming skills. So, if you find yourself in the same situation, I'll try to help you model this challenge.

The challenge asks you to calculate the minimum total cost to climb a staircase. You are given a list of costs as an array of integers, where each cost is the cost of a step. You can either climb one or two steps at a time.

In this case, we can utilize dynamic programming to determine the minimum cost to reach each step. The key concept you need to keep in mind to solve this challenge is:

At each step, the total cost to reach the current step is calculated as the minimum between the cost of the previous step and the step before that.

Translating this logic into code will result in the following snippet

// ...
for i := 2; i <= len(cost); i++ {
    oneStepBack := oneStepBackTotalCost + cost[i-1]
    twoStepBack := twoStepBackTotalCost + cost[i-2]
    minTotalCost = min(oneStepBack, twoStepBack)
    // ...
}

Now, only two things remain to finish the code:

• Initialization of the variables
• The update of oneStepBackTotalCost and twoStepBackTotalCost after each step

Initialization of the variables

Before entering the loop, no cost has been accounted yet. Therefore, we can initialize the variables to 0

minTotalCost, oneStepBackTotalCost, twoStepBackTotalCost := 0, 0, 0

The update of oneStepBackTotalCost and twoStepBackTotalCost after each step

This is the tricky part.
Since we are about to climb the next step, the cost to reach the current step will become the cost to reach the previous step in the next iteration. Hence, the cost to reach the previous step will become the cost to reach the step before that.

twoStepBackTotalCost = oneStepBackTotalCost
oneStepBackTotalCost = minTotalCost

After finishing the loop, the minimum total cost will be stored in the variable minTotalCost. Return that, and the challeng is solved.
Here is the code:

func minCostClimbingStairs(cost []int) int {
    minTotalCost, oneStepBackTotalCost, twoStepBackTotalCost := 0, 0, 0

    for i := 2; i <= len(cost); i++ {
        oneStepBack := oneStepBackTotalCost + cost[i-1]
        twoStepBack := twoStepBackTotalCost + cost[i-2]
        minTotalCost = int(math.Min(float64(oneStepBack), float64(twoStepBack)))

        twoStepBackTotalCost = oneStepBackTotalCost
        oneStepBackTotalCost = minTotalCost
    }

    return minTotalCost
}

Thanks for reading this post! I appreciate any suggestions and improvements!