Dynamic Programming

Dynamic programming is the engine behind many of the most powerful tools in modern AI. When a language model generates text, it doesn't rethink every word from scratch — it builds on the work it has already done. When a navigation app finds the fastest route, it doesn't re-examine every road each time; it reuses the best partial routes it has already computed. This concept unlocks the ability to solve problems that would otherwise be impossibly slow — problems like aligning DNA sequences, parsing grammar, and finding the most likely sequence of words in speech recognition. In your own work, it's the difference between a program that takes seconds and one that takes years. Mastering this gives you the foundation to understand why some AI systems are fast and others are not, and it prepares you for more advanced topics like reinforcement learning and sequence modeling.

Imagine you run a small delivery service and you need to find the cheapest way to travel between two cities. You have a map, but it's a complicated network of roads, each with a toll. One way to do it is to try every possible route and compare the costs. That works for a tiny map, but if you have 20 cities, the number of possible routes explodes — it's practically impossible. Now, suppose you notice something clever: if the cheapest route from city A to city B passes through city C, then the part of that route from A to C must itself be the cheapest way to get from A to C. If it weren't, you could replace that segment with a cheaper one and get a cheaper overall route. This simple observation lets you break the problem into smaller pieces. And here's the key: many of these smaller pieces are *the same* piece. The cheapest way to get from a certain city to B might be needed for many different routes. Instead of recomputing that same answer over and over, you compute it once, store it in a table, and look it up whenever you need it again. This is dynamic programming: break a big problem into overlapping subproblems, solve each one once, store the result, and combine them to get the answer.

Think of planning a dinner party where you have to cook several dishes that share ingredients. You need a certain amount of chopped onions, diced tomatoes, and grated cheese. You could chop onions once, use half in one dish, a quarter in another, and so on. If you were to follow each recipe as a separate project, you'd end up chopping the same onion multiple times. Dynamic programming is like planning the cooking so that you chop each ingredient once, store it in a bowl, and use it wherever it's needed. This is exactly the trade-off: you're spending a little extra memory (the bowls) to save a lot of time (not re-chopping). The analogy works well because the key insight is that the subproblems (chopping onions) appear in many places, and solving them once saves enormous effort. But the analogy has limits. In cooking, you can chop an onion and use it any time, but in dynamic programming, the subproblems must be *overlapping* — meaning the same subproblem appears as part of solving many different larger problems. If each dish used a totally different ingredient, you wouldn't need the tables — you'd just cook everything separately. Also, the order matters: you have to solve the subproblems in the right order, from the smallest to the largest, which in cooking is like making sure the simpler dishes are ready before the complex casserole that needs them.

Dynamic programming is a method for solving complex problems by breaking them into overlapping subproblems, solving each subproblem only once, storing the result in a table (memo or tabulation), and then combining those stored solutions to solve the original problem.

Dynamic programming sits squarely in the branch of computer science called algorithms. It's one of the three main design strategies (the others are divide and conquer and greedy). The key difference is that dynamic programming is for problems where subproblems overlap, whereas divide and conquer (like merge sort) splits a problem into independent parts. You'll see connections to Big-O notation — dynamic programming is all about reducing the time complexity from exponential to polynomial. It also relates to space-time tradeoffs: you use more memory (the storage table) to save computation time. Memoization, which you'll see in code, is a direct implementation of dynamic programming from the top down, and it is also related to caching and the space-time tradeoff.