the two preconditions for dynamic programming

Before reaching for dynamic programming, it pays to ask a simple question: is this problem actually one that DP can crack? Two boxes must both be checked. First, optimal substructure: the best answer to the whole is built from best answers to smaller pieces. Second, overlapping subproblems: those smaller pieces recur — the same small question gets asked over and over. When both hold, DP is the right tool; when either fails, you need something else.

Why both, and not just one? Optimal substructure gives you a recurrence — a way to write the answer in terms of smaller answers — so a correct recursive solution exists at all. Overlapping subproblems are what make that recurrence worth caching: if the small answers recur, storing each one and reusing it collapses an exponential blow-up into polynomial work. If you have optimal substructure but no overlap (as in merge sort, whose halves are disjoint), plain divide and conquer already suffices and a memo table just wastes space. If you have overlap but no optimal substructure (as in longest simple path), the recurrence you would memoize is simply wrong, so caching speeds up a computation that gives the wrong answer.

In practice the checklist is your design discipline. Ask: can I phrase the optimum as a choice followed by the optimum of a residual subproblem (substructure)? And: do only polynomially many distinct subproblems arise, each demanded many times (overlap)? If yes to both, define the state, write the transition, set base cases, choose an evaluation order, and you have a DP. If the substructure is there but every subproblem is unique, you have a divide-and-conquer problem instead. The two preconditions are not bureaucratic boxes — they are precisely what guarantees a DP is both correct and fast.