Dynamic Programming: General Method
Introduction to Dynamic Programming (DP)
Dynamic Programming is a method for solving complex problems by breaking them down into
simpler subproblems. It is particularly useful when the same subproblems are solved multiple
times, allowing us to store their results (memoization) and avoid redundant computations.
Dynamic Programming is typically used for optimization problems where the objective is to
maximize or minimize a value. The core idea is to solve the problem step by step by using the
solutions to smaller subproblems.
Steps in the Dynamic Programming Approach
Identify the Subproblems:
The first step is to break the problem into smaller subproblems. These subproblems should
overlap in the sense that they are solved multiple times.
Formulate the Recurrence Relation:
Express the solution of the problem in terms of the solutions to its subproblems. This is usually
done using a recursive formula (recurrence relation).
Memoization or Tabulation:
Memoization: Store the solutions of subproblems in a memory (e.g., an array or a dictionary) to
avoid redundant computations.
Tabulation: Instead of recursion, solve subproblems iteratively and store the solutions in a table
(usually a bottom-up approach).
Construct the Solution:
Once the smaller subproblems are solved, use their solutions to build up the final solution for
the original problem.
Determine Base Cases:
Define base cases that are small enough to be solved directly without recursion.
Key Concepts
Optimal Substructure: A problem has an optimal substructure if the optimal solution to the
problem can be constructed from the optimal solutions of its subproblems.
Overlapping Subproblems: When solving the same subproblem multiple times, it results in
overlapping subproblems, making dynamic programming more efficient than approaches like
divide-and-conquer for these types of problems.
Dynamic Programming Applications
0/1 Knapsack Problem:
,Problem of selecting items with given weights and values to maximize the value without
exceeding the weight limit.
Longest Common Subsequence (LCS):
Finding the longest subsequence common to two sequences.
Matrix Chain Multiplication:
Finding the optimal way to multiply a chain of matrices to minimize the number of scalar
multiplications.
Coin Change Problem:
Finding the minimum number of coins needed to make a particular amount using a set of
denominations.
Advantages of Dynamic Programming
Efficiency: By solving overlapping subproblems only once and storing their solutions, dynamic
programming reduces the time complexity of exponential problems to polynomial time.
Optimal Solutions: Dynamic programming guarantees finding the optimal solution for
optimization problems.
-------------------------------------------------------------------------------------------------------------------------------
----------------------------------------------
All-Pairs Shortest Paths
Introduction
The All-Pairs Shortest Paths (APSP) problem aims to find the shortest path between every pair
of vertices in a given weighted graph. This problem is crucial in network routing, map
applications, and various optimization problems.
There are several algorithms to solve the APSP problem, including:
Floyd-Warshall Algorithm
Johnson's Algorithm
In this guide, we will focus on the Floyd-Warshall Algorithm, which is simpler and widely used for
dense graphs.
Floyd-Warshall Algorithm
The Floyd-Warshall Algorithm is a dynamic programming algorithm used to find the shortest
paths between all pairs of vertices in a graph. It works for both directed and undirected graphs,
and it can handle negative edge weights as long as there are no negative cycles.
Key Concept:
, The algorithm incrementally improves the solution by considering each vertex as an
intermediate point between pairs of vertices.
Steps of the Floyd-Warshall Algorithm
Initialize the Distance Matrix:
Let the graph have n vertices and be represented by an adjacency matrix G where G[i][j] gives
the weight of the edge from vertex i to vertex j.
If there is no direct edge between i and j, set G[i][j] to infinity (INF), except for G[i][i] = 0 (since
the shortest path from a vertex to itself is always 0).
Iterative Update:
For each pair of vertices
i and j, check if going through another vertex k provides a shorter path. Update the distance
matrix if:
if G[i][j]>G[i][k]+G[k][j]
then update
G[i][j]=G[i][k]+G[k][j].
Repeat for All Vertices:
The algorithm checks every possible intermediate vertex
k for each pair of vertices i and j and updates their shortest paths accordingly.
Result:
After completing the algorithm, the matrix
G[i][j] will contain the shortest distance between vertex i and vertex j.
Example
Consider the following graph with 4 vertices:
From/To 1 2 3 4
1 0 3 INF 5
2 2 0 INF 4
3 INF 1 0 INF
4 INF INF 2 0
Initial distance matrix:
[
0 3 ∞ 5
2 0 ∞ 4
∞ 1 0 ∞
∞ ∞ 2 0 ]
Introduction to Dynamic Programming (DP)
Dynamic Programming is a method for solving complex problems by breaking them down into
simpler subproblems. It is particularly useful when the same subproblems are solved multiple
times, allowing us to store their results (memoization) and avoid redundant computations.
Dynamic Programming is typically used for optimization problems where the objective is to
maximize or minimize a value. The core idea is to solve the problem step by step by using the
solutions to smaller subproblems.
Steps in the Dynamic Programming Approach
Identify the Subproblems:
The first step is to break the problem into smaller subproblems. These subproblems should
overlap in the sense that they are solved multiple times.
Formulate the Recurrence Relation:
Express the solution of the problem in terms of the solutions to its subproblems. This is usually
done using a recursive formula (recurrence relation).
Memoization or Tabulation:
Memoization: Store the solutions of subproblems in a memory (e.g., an array or a dictionary) to
avoid redundant computations.
Tabulation: Instead of recursion, solve subproblems iteratively and store the solutions in a table
(usually a bottom-up approach).
Construct the Solution:
Once the smaller subproblems are solved, use their solutions to build up the final solution for
the original problem.
Determine Base Cases:
Define base cases that are small enough to be solved directly without recursion.
Key Concepts
Optimal Substructure: A problem has an optimal substructure if the optimal solution to the
problem can be constructed from the optimal solutions of its subproblems.
Overlapping Subproblems: When solving the same subproblem multiple times, it results in
overlapping subproblems, making dynamic programming more efficient than approaches like
divide-and-conquer for these types of problems.
Dynamic Programming Applications
0/1 Knapsack Problem:
,Problem of selecting items with given weights and values to maximize the value without
exceeding the weight limit.
Longest Common Subsequence (LCS):
Finding the longest subsequence common to two sequences.
Matrix Chain Multiplication:
Finding the optimal way to multiply a chain of matrices to minimize the number of scalar
multiplications.
Coin Change Problem:
Finding the minimum number of coins needed to make a particular amount using a set of
denominations.
Advantages of Dynamic Programming
Efficiency: By solving overlapping subproblems only once and storing their solutions, dynamic
programming reduces the time complexity of exponential problems to polynomial time.
Optimal Solutions: Dynamic programming guarantees finding the optimal solution for
optimization problems.
-------------------------------------------------------------------------------------------------------------------------------
----------------------------------------------
All-Pairs Shortest Paths
Introduction
The All-Pairs Shortest Paths (APSP) problem aims to find the shortest path between every pair
of vertices in a given weighted graph. This problem is crucial in network routing, map
applications, and various optimization problems.
There are several algorithms to solve the APSP problem, including:
Floyd-Warshall Algorithm
Johnson's Algorithm
In this guide, we will focus on the Floyd-Warshall Algorithm, which is simpler and widely used for
dense graphs.
Floyd-Warshall Algorithm
The Floyd-Warshall Algorithm is a dynamic programming algorithm used to find the shortest
paths between all pairs of vertices in a graph. It works for both directed and undirected graphs,
and it can handle negative edge weights as long as there are no negative cycles.
Key Concept:
, The algorithm incrementally improves the solution by considering each vertex as an
intermediate point between pairs of vertices.
Steps of the Floyd-Warshall Algorithm
Initialize the Distance Matrix:
Let the graph have n vertices and be represented by an adjacency matrix G where G[i][j] gives
the weight of the edge from vertex i to vertex j.
If there is no direct edge between i and j, set G[i][j] to infinity (INF), except for G[i][i] = 0 (since
the shortest path from a vertex to itself is always 0).
Iterative Update:
For each pair of vertices
i and j, check if going through another vertex k provides a shorter path. Update the distance
matrix if:
if G[i][j]>G[i][k]+G[k][j]
then update
G[i][j]=G[i][k]+G[k][j].
Repeat for All Vertices:
The algorithm checks every possible intermediate vertex
k for each pair of vertices i and j and updates their shortest paths accordingly.
Result:
After completing the algorithm, the matrix
G[i][j] will contain the shortest distance between vertex i and vertex j.
Example
Consider the following graph with 4 vertices:
From/To 1 2 3 4
1 0 3 INF 5
2 2 0 INF 4
3 INF 1 0 INF
4 INF INF 2 0
Initial distance matrix:
[
0 3 ∞ 5
2 0 ∞ 4
∞ 1 0 ∞
∞ ∞ 2 0 ]
