This is harder than it sounds though.
DP problems tend to be solvable in only a couple lines of code, but the tough part is deciding what to recurve on, and what to memoize.