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:
- We make the jump (finally) to an optimization problem. We want to compute the -est if something (in the case, the small-est).
- 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:
- 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.
- Similar thing with the beginning, though to a lesser extent.
- 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.