A lesson from the data structures and algorithms bootcamp. About a 14 minute read.
Dynamic programming has a reputation for difficulty that comes almost entirely from how it is usually taught, which is as a list of tables to memorise. It is one idea: a recursion whose subproblems repeat, with the answers remembered. Write the recursion first, notice the repeats, add a cache. Everything else in this lesson is about how to define the state, which is where the real difficulty lives and where most of the teaching does not go.
A problem is a DP problem when it has OPTIMAL SUBSTRUCTURE (the best answer is built from the best answers to smaller versions) and OVERLAPPING SUBPROBLEMS (those smaller versions recur). Both matter. Merge sort has optimal substructure but its subproblems never overlap, so caching would buy nothing and it is plain divide and conquer. Naive Fibonacci overlaps enormously: fib(50) computes fib(48) twice, fib(47) three times, and about 2.7 x 10^10 calls in total, almost all of them repeats. The practical test is the recursion tree from the Recursion lesson. Draw it, look for the same node appearing in two places, and if it does you have found a DP problem. If it does not, you have found a divide-and-conquer one.
The rest of this lesson continues with 6 further sections. See the full curriculum.
Browse all 536 practice puzzles