And we’re back with our study plan. The next question follows from the previous pretty naturally, now we want to find a particular path, one that is optimal in some sense. In this case, it’s the min-cost path.

So I’m coming around to the approach presented in this study plan. There is a design behind it; my concern is that the design is a bit opaque to the new student. I can see it as someone familiar with the topic and knowing what ideas to build up to. In this question:

1. We make the jump (finally) to an optimization problem. We want to compute the -est if something (in the case, the small-est).
2. The syntax of the solution will present a lot of the common patterns to look for: you have a recurrence that basically feeds off of previous elements from the table you’re building, as well as a component of the input.

Wishlist

There are some rough edges to this question. Again, I’m coming around to this approach, but if I could ask for some things:

1. The question itself is a bit ambiguous. The effect is that the best answer is either ending on the last, or the second-to-last step. I wonder how the question would look if you always had a cost-0 step at the end. You’d end up in the same place, and I think it’d help remove ambiguity about where the path actually has to end.
2. Similar thing with the beginning, though to a lesser extent.
3. My approach, and maybe due to my own limitation, ended up with slightly different offsets from i in my new table (minCost) and the input table (cost). If/when I teach this, I’d want to make sure those indices line up in the material I present.

With that final caveat, here’s my quick solution.

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        # trusting the invariants than len(cost) > 1
        minCost = [0, cost[0], cost[1]]
        # mincost[i-1] is the min-cost of landing on that step
        for i in range(2, len(cost)):
            minCost.append(min(minCost[-1], minCost[-2])+cost[i])
        # we essentially can either end on the last, or second-to-last, step
        return min(minCost[-1], minCost[-2])
            

I’m trying to collect all the study-plan questions under this tag. All dynamic programming questions go under this other tag.