Comment by dgacmu

The hard part is realizing that the problem you're solving efficiently maps to a dynamic programming algorithm. You have to spot the opportunity for sub-problem reuse, or else the solution looks something like cubic or exponential (etc.)