I stumbled. Even though I knew the question is ultimately dynamic programming question, I struggled to get the recurrence right. The interviewer was extremely helpful in giving guidance and keeping me on track. Eventually I coded it up, but took me more time than it should have.