A lesson from the Algorithms & Patterns module of the bootcamp. About a 14 minute read.
Dynamic programming has a reputation for being hard, and that reputation comes almost entirely from how it is usually taught: as a list of tables to memorize. 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 defining the state, which is where the real difficulty lives and where most teaching never goes.
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 come up again and again). Both matter. Merge sort has optimal substructure, but its subproblems never overlap, so caching would buy nothing. It is plain divide and conquer. Naive Fibonacci overlaps enormously: fib(50) computes fib(48) twice, fib(47) three times, and makes 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 and look for the same node in two places. If you find one, it is a DP problem. If not, it is divide and conquer.
The rest of this lesson continues with 6 further sections. See the full curriculum.
Browse all 576 practice puzzles