[mercutio2]

Many great engineers get pretty stuck when I ask this question; they try to do dynamic programming and unless they get lucky they get a little lost.

If I ask them to draw a picture, they get your solution pretty much immediately.

So I put this problem in the “gotcha” drawer, because it basically depends on having a eureka moment to get the easy solution.

Still fun to pull it out, but more as extra credit than as a useful interview question.