Unveiling Dynamic Programming: Simplifying Complex Problem

 

In the field of computer science, dynamic programming (DP) is an important technique that deals with solving problems by decomposing the larger problem into small sub-problems that have already been resolved by the system. This is especially useful in problems involving optimization, that is, selecting the optimal solution from many available solutions. As we promised, in this blog post, we shall explain dynamic programming from the ground up, provide a sample code, and also provide real-life examples that will help people who never read any computer science book or CS literature to easily understand the concept.

Dynamic Programming

Dynamic programming is an optimization technique that solves today’s complex problems by decomposing them into smaller, simpler, and overlapping subproblems. This avoids solving the same subproblem over and over by storing solutions to the subproblems. The next time a certain subproblem is encountered, rather than repeating the set of calculations it takes to find a solution, one just refers to the previous calculation results. This technique is often used when searching for the solutions of optimal substructure and overlapping subproblems.

Coding Example: Fibonacci Sequence

Dynamic programming is applicable in solving problems like the Fibonacci sequence without needing recursion. The sequence is defined as follows:

• The initial state is 𝐹(0)=0F(0)=0.
• 𝐹(1)=1F(1)=1.
• For any integer 𝑛n greater than or equal to 2, 𝐹(𝑛)F(n) is defined as: 𝐹(𝑛)=𝐹(𝑛−1)+𝐹(𝑛−2)F(n)=F(n−1)+F(n−2)

Let’s implement this using dynamic programming in Python:

def fibonacci(n):
    # Create a list of size n + 1 and initialize all list elements as 0
    fib = [0] * (n + 1)
    
    # Set up the first two Fibonacci numbers
    fib[0] = 0
    fib[1] = 1
    
    # Use the above equation to determine the other subsequent Fibonacci numbers
    for i in range(2, n + 1):
        fib[i] = fib[i - 1] + fib[i - 2]
    
    return fib[n]

# Example usage
n = 10
print(fibonacci(n))  # Output: 55

Real-Life Analogies of Dynamic Programming

As it’s always easier to learn new concepts when those concepts are set in context, let’s now think about everyday examples that demonstrate the fundamentals of dynamic programming.

1. The Supermarket Shopping List

Imagine a shopping trip to a supermarket. You use a list of things that need to be bought, and there are items that are purchased more than once for different meals in a week.

Dynamic Programming Approach:

• Subproblems: All the items in the list are subproblems.
• Overlapping Subproblems: Some items are needed for multiple meals.
• Optimal Substructure: The overall shopping list can be optimized by determining whether there are scenarios that require purchasing basics to cover all the various meal plans.

Instead of continuing to place the same items in the list again and again, you develop one list where each item is only put once, so as to avoid repurchasing what has already been bought. This saves time and effort, similar to how an efficient DP approach saves time by solving subproblems only once and then reusing the solutions.

2. The Puzzle Solver

Consider a novel you enjoy reading, which you’d like to adapt as a game based on your favorite pastime. In this work, each element combines and interrelates perfectly to form the final whole of the picture.

Dynamic Programming Approach:

• Subproblems: The puzzle pieces represent subproblems since they fit together to form a comprehensive puzzle map.
• Overlapping Subproblems: Some pieces may take a long time to locate the right intersection where they fit properly.
• Optimal Substructure: The picture is only complete once one sees how every single subproblem fits or how every piece of the jigsaw puzzle is placed.

This way of solving a problem by dividing it into smaller parts (subproblems) and using solutions to those parts to solve the whole problem (overlapping subproblems) enables the whole problem to be solved efficiently.

3. The Marathon Training Plan

Assume you have planned your training for a marathon and have a weekly running routine. Each week has increasing mileage from the previous week’s training program.

Dynamic Programming Approach:

• Subproblems: Each week’s training schedule is a subproblem.
• Overlapping Subproblems: Weekly plans may include iterations of activities, for example, running a specified number of miles on the recommended days of the week.
• Optimal Substructure: Your final readiness for the marathon will depend on the training done over the corresponding number of weeks.

You do not need to plan the week starting from scratch. Instead, you can create a more dynamic plan that allows achieving better results because you do not spend time repeating the same thing that might not help build up stamina.

Expalining all above examples with code:

1. The Puzzle Solver

We’ll simulate solving a jigsaw puzzle by finding and combining pieces.

def solve_puzzle(pieces):
    # Create a dictionary to store the solution
    solution = {}
    
    for piece in pieces:
        position = piece['position']
        image = piece['image']
        solution[position] = image
    
    return solution
# Example puzzle pieces
pieces = [
    {'position': (0, 0), 'image': 'Corner Piece'},
    {'position': (0, 1), 'image': 'Edge Piece'},
    {'position': (1, 0), 'image': 'Edge Piece'},
    {'position': (1, 1), 'image': 'Center Piece'}
]
puzzle_solution = solve_puzzle(pieces)
print("Puzzle Solution:", puzzle_solution)

Output:

Puzzle Solution: {(0, 0): 'Corner Piece', (0, 1): 'Edge Piece', (1, 0): 'Edge Piece', (1, 1): 'Center Piece'}

2. The Marathon Training Plan

We’ll simulate creating a training plan that builds on the previous week’s mileage.

def create_marathon_training_plan(weeks):
    # Initialize the training plan with a base mileage
    training_plan = [0] * weeks
    training_plan[0] = 10  # Starting mileage for week 1
    
    # Build the training plan by increasing mileage each week
    for week in range(1, weeks):
        training_plan[week] = training_plan[week - 1] + 2  # Increment by 2 miles each week
    
    return training_plan
# Example training plan for 8 weeks
weeks = 8
training_plan = create_marathon_training_plan(weeks)
print("Marathon Training Plan:", training_plan)

Output:

Marathon Training Plan: [10, 12, 14, 16, 18, 20, 22, 24]

These examples provide a practical application of the dynamic programming principles, showcasing how breaking down problems into manageable subproblems and reusing solutions can optimize and simplify complex tasks.

Conclusion

The concept of dynamic programming is understood to be the subdividing of a large-scale problem into more manageable problems which need to be solved only once. The solutions to these problems are then used again in order to arrive at the final solution. Whether you are a coder trying to optimize the code for Fibonacci sequence generation, planning your grocery list, solving a jigsaw puzzle, or sweating out on a marathon, you can use the principles of dynamic programming to optimize tasks most efficiently. Once you understand and know how to utilize DP, you can address numerous issues in computer science as well as your day-to-day existence.