As an interviewer, I would not mind seeing a "naive" recursive solution first, though I would want the interview candidate to either mention this before implementing the recursive solution or later when they "discover" the inefficiencies. Showing your work (and describing your thought process) can provide more insight to an interviewer than just popping out an optimal solution without explanation!