Dynamic Programming - Step by Step Guide with Examples
Dynamic programming is a method for solving complex problems by breaking them down into smaller subproblems. It is a mathematical optimization technique that is mainly used for solving problems that exhibit the properties of overlapping subproblems and optimal substructure.
The basic idea behind dynamic programming is to solve a complex problem by breaking it down into smaller subproblems, solving each of those subproblems just once, and storing their solutions. The solutions to the subproblems are then used to solve the original problem.
Here is a step-by-step guide to understanding dynamic programming with examples:
1. Identify the subproblems
The first step in using dynamic programming to solve a problem is to identify the subproblems that make up the original problem. These subproblems should be small enough to be solved independently, but they should also be related to the original problem in some way.
For example, suppose we want to find the shortest path between two points on a map. In this case, the subproblems would be the individual segments of the path between the start and end points. Each subproblem would involve finding the shortest path between two adjacent points on the map.
2. Develop a recursive solution
Once the subproblems have been identified, the next step is to develop a recursive solution to the original problem. This means expressing the solution to the original problem in terms of solutions to the subproblems.
For example, suppose we want to find the shortest path between two points on a map, and we have already identified the subproblems as the individual segments of the path. We can then develop a recursive solution by expressing the shortest path between the start and end points in terms of the shortest paths between the intermediate points on the path.
3. Store the solutions to the subproblems
The next step is to store the solutions to the subproblems so that they can be used to solve the original problem. This is where the "programming" part of dynamic programming comes in. We need to create a data structure (such as an array or a hash table) to store the solutions to the subproblems.
For example, suppose we want to find the shortest path between two points on a map, and we have already identified the subproblems and developed a recursive solution. We can store the solutions to the subproblems in an array, with the array index representing the position on the map and the array value representing the shortest path from the start to that position.
4. Use the stored solutions to solve the original problem
The final step is to use the stored solutions to the subproblems to solve the original problem. This is done by using the recursive solution developed in step 2 and the stored solutions to the subproblems to compute the solution to the original problem.
For example, suppose we want to find the shortest path between two points on a map, and we have already identified the subproblems, developed a recursive solution, and stored the solutions to the subproblems. We can then use the stored solutions to compute the shortest path between the start and end points by applying the recursive solution to the stored solutions.
Dynamic programming is a powerful technique for solving complex problems, but it can be difficult to understand and apply. However, by following the steps outlined above, you can gain a better understanding of how dynamic programming works and how to use it to solve problems.
Different Approaches for Dynamic Programming
There are two main approaches to dynamic programming: the top-down approach and the bottom-up approach.
Top-down approach
The top-down approach to dynamic programming involves solving the original problem by breaking it down into smaller subproblems and solving each of those subproblems recursively. This approach is also known as memoization, because it involves storing the solutions to the subproblems in a memo (i.e. a data structure such as an array or a hash table) and using them to solve the original problem.
The top-down approach is typically implemented using recursion. For example, suppose we want to find the shortest path between two points on a map. We can use the top-down approach to solve this problem by developing a recursive function that takes the current position on the map as an argument and returns the shortest path from the start to that position. The function would then be called recursively to compute the shortest path between the intermediate points on the map.
Here is an example of the top-down approach to dynamic programming in Python:
1def shortest_path_top_down(map, start, end):
2 # Store the solutions to the subproblems in a memo
3 memo = {}
4
5 # Define a recursive function to compute the shortest path between two points on a map
6 def shortest_path_recursive(current):
7 # If the current position is the end position, return 0
8 if current == end:
9 return 0
10
11 # If the current position has already been visited, return the stored solution
12 if current in memo:
13 return memo[current]
14
15 # Set the minimum path length to infinity
16 min_path_length = float("inf")
17
18 # Iterate over the adjacent positions
19 for next_pos in map[current]:
20 # Compute the shortest path to the next position using the recursive solution
21 path_length = 1 + shortest_path_recursive(next_pos)
22
23 # Update the minimum path length
24 min_path_length = min(min_path_length, path_length)
25
26 # Store the minimum path length in the memo
27 memo[current] = min_path_length
28
29 # Return the minimum path length
30 return min_path_length
31
32 # Call the recursive function to compute the shortest path between the start and end points
33 return shortest_path_recursive(start)
34
35
36if __name__ == "__main__":
37 # Define the map
38 map = {
39 "A": ["B", "C"],
40 "B": ["D", "E"],
41 "C": ["F"],
42 "D": [],
43 "E": ["F"],
44 "F": []
45 }
46
47 # Define the start and end points
48 start = "A"
49 end = "F"
50
51 # Compute the shortest path between the start and end points
52 shortest_path_length = shortest_path_top_down(map, start, end)
53
54 # Print the shortest path length
55 print(shortest_path_length) #
Bottom-up approach
The bottom-up approach to dynamic programming involves solving the smaller subproblems first and then using their solutions to solve the original problem. This approach is also known as tabulation, because it involves storing the solutions to the subproblems in a table (i.e. an array or a matrix) and using them to compute the solution to the original problem.
The bottom-up approach is typically implemented using iteration. For example, suppose we want to find the shortest path between two points on a map. We can use the bottom-up approach to solve this problem by iterating over the positions on the map and computing the shortest path from the start to each position using the solutions to the subproblems (i.e. the shortest paths to the adjacent positions).
Here is an example of the bottom-up approach to dynamic programming in Python:
1# Function to compute the shortest path between two points on a map using the bottom-up approach
2def shortest_path_bottom_up(map, start, end):
3 # Store the solutions to the subproblems in an array
4 shortest_paths = [float("inf")] * (len(map) + 1)
5
6 # Set the shortest path from the start to the start to 0
7 shortest_paths[start] = 0
8
9 # Iterate over the positions on the map
10 for i in range(1, len(map) + 1):
11 # If the current position is not the end position
12 if i != end:
13 # Iterate over the adjacent positions
14 for next_pos in map[i]:
15 # Compute the shortest path to the next position using the recursive solution
16 path_length = 1 + shortest_paths[next_pos]
17
18 # Update the shortest path to the current position
19 shortest_paths[i] = min(shortest_paths[i], path_length)
20
21 # Return the shortest path from the start to the end
22 return shortest_paths[end]
This function takes the map (as a list of lists of adjacent positions), the start position, and the end position as arguments, and returns the shortest path between the start and end positions. The function stores the solutions to the subproblems in an array and uses them to compute the shortest path between each position on the map.
Author: Sadman Kabir Soumik