The two properties, checked before you write code

A notebook only helps if the same question comes up more than once, and only works if the answer to a big question can be built from answers to smaller ones. Those are the two properties, and checking them takes about thirty seconds.

Overlapping subproblems

The same smaller question is asked repeatedly.

Climbing stairs has it: ways(3) is needed by both ways(4) and ways(5).

Merge sort does not. It splits an array into two halves and neither half is ever asked about again. That is why merge sort is divide and conquer and not dynamic programming, despite both being recursive.

Optimal substructure

The best answer to the whole problem is built from best answers to its parts.

Shortest path has it. If the shortest route from Chennai to Delhi goes through Nagpur, then the part from Chennai to Nagpur must itself be the shortest route between those two. If it were not, you could swap in the shorter one and improve the whole thing, which contradicts it being best.

Longest simple path does not have it, which is worth knowing because it looks as though it should. Gluing the longest path from A to B onto the longest path from B to C can revisit a city, and the result is not a simple path at all.

Using this in an interview

Say it out loud before you start coding:

The same subproblem appears many times, and the best answer uses best answers to smaller versions. So this is dynamic programming.

If you cannot say that sentence about the problem in front of you, DP is probably the wrong tool, and page twelve is about what to reach for instead.