Dynamic
Programming:
Mastering
Optimization
Dynamic programming is a powerful algorithmic technique that
revolutionizes the way we solve complex optimization problems. This
presentation will explore the general method and delve into its
diverse applications, from optimal binary search trees to the intriguing
Travelling Salesman Problem.
by Kiranmai Devarakonda
Dynamic
Programming: The
General Method
1 Divide and Conquer 2
Optimal Substructure
Break down the problem Identify the optimal
into smaller, overlapping solution to the overall
subproblems that can be problem can be
solved independently. constructed from optimal
solutions to the
subproblems.
3 Memoization
Store and reuse solutions to subproblems to avoid redundant
computations, ensuring efficiency.
Optimal Binary Search Tree
1 Define the Problem
Given a set of keys and their access probabilities, find the
optimal binary search tree that minimizes the expected
search time.
2 Recursive Formulation
The optimal cost of a subtree rooted at a given node is
the sum of the root's cost and the optimal costs of the left
and right subtrees.
3 Dynamic Programming Solution
Build a table of optimal costs, filling in the table in a
bottom-up manner to find the overall optimal cost.
0/1 Knapsack Problem
The Problem Recursive Formulation Dynamic Programming
Approach
Given a set of items with weights The optimal value for a given weight
and values, find the subset of items capacity is the maximum of either Build a 2D table to store the optimal
that maximizes the total value while including the current item or values, filling it in a bottom-up
respecting the weight capacity of excluding it. manner to find the overall optimal
the knapsack. solution.
All Pairs Shortest Path
1 The Problem
Find the shortest paths between all pairs of nodes in a
weighted graph.
2 Recursive Formulation
The shortest path between two nodes can be found by
considering all possible intermediate nodes that could be
used to reach the destination.
3 Dynamic Programming Solution
The Floyd-Warshall algorithm iteratively updates a 2D
table of shortest path distances between all pairs of
nodes.
Travelling Salesman Problem
The Problem
Find the shortest possible tour that visits each city exactly
once and returns to the starting city.
Recursive Formulation
The optimal tour can be found by considering all possible
permutations of city visits and choosing the one with the
minimum total distance.
Dynamic Programming Approach
Use a 2D table to store the minimum cost of visiting a subset
of cities, starting from a given city.
Principles of Dynamic Programming
Overlapping Subproblems Optimal Substructure
Dynamic programming exploits the fact that many The optimal solution to a problem can be constructed from
subproblems are repeated, allowing for efficient reuse of optimal solutions to its subproblems.
solutions.
Memoization Bottom-up Approach
Storing and reusing solutions to subproblems to avoid Building solutions to larger problems by iteratively solving
redundant computations, ensuring efficiency. smaller subproblems, starting from the base cases.
Key Takeaways
Divide and Conquer Optimal Substructure
Break down problems into Identify how optimal solutions to
smaller, overlapping subproblems can be combined to
subproblems. solve the original problem.
Memoization Bottom-up Approach
Store and reuse solutions to Build solutions to larger problems
subproblems to avoid redundant by iteratively solving smaller
computations. subproblems.