Gas Station Minimum Cost Problem
Introduction to Dynamic Programming
Solving Problems in Pieces
Imagine you're trying to solve a giant jigsaw puzzle. You wouldn't just stare at the whole mess of pieces and hope for the best. A better strategy is to find smaller, manageable sections, like the corners or a patch of a specific color. You solve those small sections first, and then you piece those solved sections together to complete the entire puzzle.
Dynamic programming (DP) is a problem-solving technique that works in a similar way. It's a method for tackling large, complex problems by breaking them down into simpler, smaller subproblems. You solve each subproblem just once, store its solution, and then use those solutions to build up to the answer for the main problem.
Dynamic Programming is a method used to solve complex problems by breaking them down into simpler subproblems.
The Two Key Ingredients
Dynamic programming isn't a magic wand for every problem. It only works when a problem has two specific characteristics: optimal substructure and overlapping subproblems.
substructure
noun
The property where the optimal solution to a larger problem can be constructed from the optimal solutions of its smaller subproblems.
Think about finding the shortest driving route from San Francisco to New York City. Let's say the best route goes through Denver. If that's true, then the path you took from San Francisco to Denver must be the shortest possible path between those two cities. If there were a shorter route to Denver, you could just swap it in to get an even shorter total trip to NYC. That's optimal substructure in action.
The second ingredient is overlapping subproblems. This means that when you break the main problem down, you find yourself needing to solve the exact same subproblem multiple times.
The classic example is calculating Fibonacci numbers. The sequence starts with 0 and 1, and each subsequent number is the sum of the two preceding ones. To find the 5th Fibonacci number, , you need to calculate and . But to calculate , you need and . Notice that is needed in both calculations. A simple recursive approach would calculate it twice, which is inefficient. Dynamic programming saves the result of the first time and just looks it up the second time.
Two Flavors of DP
Once you've identified a problem that's a good fit for dynamic programming, there are two main approaches you can take to solve it.
1. Top-Down with Memoization
This approach feels very natural. You write a recursive function that works from the top (the original problem) down to the base cases. As you solve each subproblem, you store, or "memoize," its result in a cache (like an array or a hash map). Before computing a subproblem, you check the cache. If the answer is already there, you just use it. If not, you compute it, save it, and then return it.
Think of it as working with a very lazy, but smart, contractor. You ask for a house (the big problem). The contractor checks their notes. Have they built this exact house before? No. Okay, to build the house, they need a foundation. Have they built this exact foundation before? And so on. Once they build something, they jot it down in their notebook so they never have to figure it out again.
2. Bottom-Up with Tabulation
This approach is more like building with LEGOs. You start with the smallest, most basic subproblems and solve them first. You store these results in a table (hence, tabulation). Then you work your way up, using the results of the simpler subproblems to solve slightly larger ones, until you've built up the solution to the original problem.
For the Fibonacci sequence, you wouldn't start at . Instead, you'd calculate , then . With those, you can calculate . Then , and so on, filling your table until you get to . You solve all the necessary subproblems in a logical order, from smallest to largest.
| Approach | Method | How it Works |
|---|---|---|
| Top-Down | Recursion + Caching | Starts with the main problem and breaks it down. Stores results along the way. |
| Bottom-Up | Iteration + Table | Starts with the smallest subproblems and builds up to the main solution. |
Both approaches solve the same subproblems and give the same final answer. The choice between them often comes down to the specific problem structure or personal preference. The bottom-up approach can sometimes be faster as it avoids the overhead of recursive function calls.
Dynamic programming is an effective strategy for problems that exhibit which two characteristics?
A programmer is calculating the 20th Fibonacci number, . They notice that their simple recursive function calculates the value for many different times throughout the process. This redundancy is an example of which key dynamic programming concept?
Dynamic programming is a versatile tool used in everything from genetics (sequence alignment) to routing algorithms that find the shortest path in a network. By breaking problems down and remembering past results, it provides an efficient way to find optimal solutions.