Ask a computer to calculate the 40th Fibonacci number using the most obvious, textbook-recursive approach — each number defined as the sum of the two before it — and it can take several seconds, even though the answer is just a single integer. Ask for the 50th, and it can take minutes. The problem isn't the arithmetic; a computer can do billions of additions per second. The problem is that the naive recursive approach ends up calculating the exact same smaller Fibonacci numbers over, and over, and over again, an enormous and completely avoidable amount of repeated, wasted work.
The redundancy hiding inside naive recursion
Computing the 5th Fibonacci number the naive recursive way requires computing the 4th and 3rd. Computing the 4th requires computing the 3rd and 2nd again — a second, entirely separate calculation of the 3rd Fibonacci number that produces the identical answer as before, for no new information at all. This redundancy compounds explosively: the naive approach ends up making roughly two calls for every one it needs to make usefully, doubling (very roughly) with each additional step, which produces a runtime that grows exponentially with the input size. A problem that should take microseconds instead takes an amount of time that grows completely out of control as the input gets only modestly larger.
Dynamic programming: solve each subproblem exactly once
Dynamic programming fixes this with a conceptually simple idea: store the answer to each distinct subproblem the first time it's solved, and look it up instead of recalculating it every time it's needed again. Applied to Fibonacci, this means calculating each number from 1 up to 40 exactly once, in order, storing each result, and reusing stored results for every later calculation that needs them — collapsing what was an exponential number of redundant calculations down to a number that grows only in direct proportion to the input size. The technique applies far beyond simple textbook examples like Fibonacci: dynamic programming is the standard approach behind route-finding algorithms, DNA sequence alignment in bioinformatics, and a wide range of optimisation problems where a large problem can be broken into smaller, overlapping subproblems that would otherwise be recalculated wastefully many times over.
What we're still unsure about
Dynamic programming's core mechanism — storing and reusing solutions to overlapping subproblems — is a well-established, precisely analysable technique, and this isn't a matter of debate. The genuinely hard, still largely unsolved problem is recognising, for a brand-new problem nobody has already mapped a dynamic programming solution for, whether it actually has the right structure (overlapping subproblems and what's called "optimal substructure") to benefit from the technique at all, and if so, exactly how to define the right subproblems to store. There's no general, automatic procedure that reliably spots this opportunity in an arbitrary new problem — it remains something that typically requires genuine problem-specific insight, which is part of why dynamic programming is often considered one of the more conceptually demanding tools in an algorithms toolkit, even though the underlying idea, once explained, sounds almost too simple to be powerful.
This sits inside Dynamic Programming, one of eight topics in Algorithms, one of seven domains in Computer Science, one of seventeen subjects the app can quiz you on.