This one I’ve taught many times. I have it in my archives, and in my old lectures notes. It’s the first “day 2” exercise for the study plan.

The punchline, of course, is that you end up with the fibonacci sequence again. I do appreciate that they’re articulating the question as “choosing” between two options… but with the head-fake that you’re calculating the number of choices, which of course is fixed. So we’re still not really choosing anything! I am sympathetic to the idea that this is how we’re getting closer to the concepts that underly “real” dynamic programming, but I’ve seen enough confusion on the matter where I can’t say that’s intentional.

Though, that said, I do recall when I taught a lesson on this, I think we were able to get some practice in on the idea of taking 2 previous solutions, and “building” off of those. I do think this is a much better first question than fibonacci. On the other hand, it took probably 60 minutes (half of my 2-hour session) to go over this… not exactly a warm-up question if the audience is learning dynamic programming (versus reviewing it).

Anyways, here’s the solution, with a slight off-by-one difference from the last time.

class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1: return 1
        if n == 2: return 2
        a = [1, 2]
        for i in range(2, n):
            a.append(a[i-1]+a[i-2])
        return a[-1]

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