1. What is Dynamic Programming?
Dynamic Programming is an algorithmic paradigm that solves a given complex problem by breaking it into sub-problems and stores the results of sub-problems to avoid computing the same results again.
Dynamic programming is used where we have problems, which can be divided into similar sub-problems, so that their results can be re-used. Mostly, these algorithms are used for optimization. Before solving the in-hand sub-problem, dynamic algorithm will try to examine the results of the previously solved sub-problems. The solutions of sub-problems are combined in order to achieve the best solution.
2. Optimal Substructure and Overlapping Sub-problems
There are two key attributes that a problem must have in order for dynamic programming to be applicable: optimal substructure and overlapping sub-problems.
2.1 Optimal Substructure
Optimal substructure means that the solution to a given optimization problem can be obtained by the combination of optimal solutions to its sub-problems. Such optimal substructures are usually described by means of recursion.
For example - Given a graph G=(V,E), the shortest path p from a vertex u to a vertex v exhibits optimal substructure: take any intermediate vertex w on this shortest path p. If p is truly the shortest path, then it can be split into sub-paths p1 from u to w and p2 from w to v such that these, in turn, are indeed the shortest paths between the corresponding vertices. Hence, one can easily formulate the solution for finding shortest paths in a recursive manner, which is what the Bellman–Ford algorithm or the Floyd–Warshall algorithm does.
2.2 Overlapping Sub-problems
Overlapping sub-problems means that the space of sub-problems must be small, that is, any recursive algorithm solving the problem should solve the same sub-problems over and over, rather than generating new sub-problems.
For example - Consider the recursive formulation for generating the Fibonacci series: Fi = Fi−1 + Fi−2, with base case F1 = F2 = 1. Then F43 = F42 + F41, and F42 = F41 + F40. Now F41 is being solved in the recursive sub-trees of both F43 as well as F42. Even though the total number of sub-problems is actually small (only 43 of them), we end up solving the same problems over and over if we adopt a naive recursive solution such as this. Dynamic programming takes account of this fact and solves each sub-problem only once.
This can be achieved in either of two ways:
Top-down approach: This is the direct fall-out of the recursive formulation of any problem. If the solution to any problem can be formulated recursively using the solution to its sub-problems, and if its sub-problems are overlapping, then one can easily memorize or store the solutions to the sub-problems in a table. Whenever we attempt to solve a new sub-problem, we first check the table to see if it is already solved. If a solution has been recorded, we can use it directly, otherwise we solve the sub-problem and add its solution to the table.
Bottom-up approach: Once we formulate the solution to a problem recursively as in terms of its sub-problems, we can try reformulating the problem in a bottom-up fashion: try solving the sub-problems first and use their solutions to build-on and arrive at solutions to bigger sub-problems. This is also usually done in a tabular form by iteratively generating solutions to bigger and bigger sub-problems by using the solutions to small sub-problems. For example, if we already know the values of F41 and F40, we can directly calculate the value of F42.
3. List of Algorithms based on Dynamic Programming
The Dynamic Programming is quite powerful and works well for a wide range of problems. Many algorithms can be viewed as applications of the Greedy algorithms, such as :
- Fibonacci number series
- Knapsack problem
- Tower of Hanoi
- All pair shortest path by Floyd-Warshall
- Shortest path by Dijkstra
- Project scheduling
4. Example - Fibonacci Number Series
The Fibonacci numbers are the numbers in the following integer sequence.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ....
In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the recurrence relation
F(n) = F(n)-1 + F(n)-2, where F(0) = 0 and F(1) = 1
4.1 Top-down approach
In this example, we initialize a lookup array with all initial values as -1. Whenever we need solution to a subproblem, we first look into the lookup array. If the precomputed value is there then we return that value, otherwise we calculate the value and put the result in lookup array so that it can be reused later.
#include <stdio.h>
#define MAX 100
int lookup[MAX];
/* Function to initialize NIL values in lookup table */
void initialize()
{
int i;
for (i = 0; i < MAX; i++)
{
lookup[i] = -1;
}
}
/* function for nth Fibonacci number */
int fib(int n)
{
if (lookup[n] == -1)
{
if (n <= 1)
{
lookup[n] = n;
}
else
{
lookup[n] = fib(n-1) + fib(n-2);
}
}
return lookup[n];
}
int main() {
int n = 9;
initialize();
printf("%d\n", fib(n));
return 0;
}
//output: 34
4.2 Bottom-up approach
In this example, for the same Fibonacci number, first we calculate fib(0) then fib(1) then fib(2) then fib(3) and so on. So literally, we are building the solutions of subproblems bottom-up.
#include <stdio.h>
int fib(int n)
{
int f[n+1];
int i;
f[0] = 0; f[1] = 1;
for (i = 2; i <= n; i++)
{
//Add the previous 2 numbers in the series and store it
f[i] = f[i-1] + f[i-2];
}
return f[n];
}
int main() {
int n = 9;
printf("%d\n", fib(n));
return 0;
}
//output: 34
