Last updated 29 days ago

DP’s secret: think globally optimal, not just locally.

You have to break the problem into simpler subproblems, solving each of them just once, and building the solution combining these solved subproblems

The opposite of DP is a greedy algorithm because the latter picks the locally optimal choice at each step. And locally optimal choices may result in a bad global solution.