This is just a quick note to log how I understand Dynamic Programming after listening to the lecture in class today.
Dynamic programming (DP) is very similar to the Divide and Conquer algorithm. The main difference is that in DP, the subproblems tend to repeat.
There are three core ideas to remember about DP:
1. Optimal Substructure
Like Divide and Conquer, a big problem is broken down into many smaller subproblems. We can solve the main problem by finding and selecting the optimal outputs of these subproblems.
- Example (Floyd-Warshall Algorithm): To find the shortest paths between all pairs of vertices in a graph, we break it down by finding the shortest path between each specific pair (u, v) first. Combining these optimal sub-answers gives us the final solution for the entire graph.
2. Overlapping subproblems
in DP, the same subproblems show up over and over again. Instead of recalculating the exact same answer every time, DP solves it once, saves the result, and reuses it later.
- Example: Imagine you want to find the shortest path to school from two different starting locations: your home and your grandparent's house. Both routes must pass through the stationary store to reach school Path(home -> school) = dis(home -> store) + dis(store -> school) Path(grandparent->school) = dis(grandparent -> store) + dis(store -> school)
as you can see, the fragment dis(store -> school) is shared. DP calculates this distance once, saves it, and instantly reuses it for both routes.
3. Table-Based Solution Tracking
To build the final solution, DP keeps track of all sub-problem answers in a table (often called a DP table or memoization table). This is how we synthesize everything together.
- Example: Suppose from your home, you can choose to pass through either a grocery store, a convenience store or a book store to get to school.
- Your subproblems are finding the shortest path from home to each store to the school. DP saves all these options in a table. In the end, you look at the table, compare the total costs, and pick the single best store to pass through to minimize your travel time.
Top comments (0)