I used dynamic programming techniques and hand-wrote some Java/pseudocode to solve the problem. I felt a little rusty in the interview, so I made sure to talk through what I was doing and that really helped.