DP solution is OK when interviewing for a junior positon, but may not cut it otherwise. Dear authors, please at least mention that there is a faster solution based on a monotonic sequence. In fact, I think that it’s quite natural to arrive at that solution after understanding the tabulation.
2 Likes