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 t

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.