Dynamic Programming: An Introduction
Join the DZone community and get the full member experience.
Join For FreeIntroduction
By considering a number of different algorithms, we can begin to develop pattern recognition so that the next time a similar problem arises, we are better able to solve it. There will often be trade-offs that we will need to identify and decide upon. Divide and conquer strategy, optimization problem, dynamic programming, and backtracking have mostly similar challenges and difficulties, such as constraints, recurrence relation, greedy, multiple objectives, discrete, and variables.
In order to tackle each of these difficulties, we need to know principals and general algorithms and master theorems in a practical approach to optimize the execution time of our algorithms.
Divide and Conquer Strategy
This strategy breaks a problem into subproblems that are similar to the main problem and then recursively solves the subproblems. Finally, it combines the solutions to the subproblems of original problems. Imagine P is a problem with the size of n, and S is the solution.
In this case, P is large enough to be divide into a subproblem, for example, P1, P2, P3, P4, ... , Pk (let's say k subproblems), and let's say there are k solutions for each of k subproblems, like S1, S2, S3, ... , Sk. Now, if we combine each solution of subproblem together, we can get the S result. In the divide and conquer strategy, whatever is the main problem must also be the same for all subs problems. For example, if P is sort then the P1, P2 and Pn must be sort too. The general schema of a divide and conquer strategy looks like:
DivideAndConquer(P)
{
if(is_small(p)) {
SolutionOf(P);
} else {
Divide P into P1, P1, ... , Pk;
DivideAndConquer(P1), ... , DivideAndConquer(Pn);
Combine(DivideAndConquer(P1) , ... , DivideAndConquer(Pn));
}
}
As you see, a recurrence relation is in the nature of the Divide and Conquer strategy.
Optimization Problem
Optimization problems are problems that demand either minimum or maximum results. Suppose there is a problem P: A -> B, It goes from city A to city B. It can go from A to B via walk, car, bike, TGV, bicycle or a flight. In this case, all options are available. But, if there's a constraint, like this path should be paved in 12 hours. Now, suppose you can only use an airplane or TGV to arrive at your destination on time. You can not cover it by walk or bike or etc.
Basically, only the airplane and TGV are feasible options here. Feasible solutions (options) are kinds of solutions that satisfy the condition(s) of the problem. In fact, if the problem has a condition, the final result can be found only in a feasible solution. If the above problem changes and asks you to pave this path with minimum cost, then, this problem will be an optimization problem.
In algorithm design, our optimization problems are closed (Bounded) intervals. The basic idea of the optimization problems is the same, as we have a particular quantity that we are interested in maximizing or minimizing. However, we also have some auxiliary condition that needs to be satisfied. There are three main strategies for solving Optimization problems: Greedy method, Dynamic Programming, and Branch and Bound.
Greedy Method
A greedy method, as the name suggests, always makes the choice that seems to be the best at that moment. This method is mostly used for solving an optimization problem. The greedy method says that a problem should be solved in stages; in each stage, it considers input from the given problem, and if the input is feasible, then it will add it to the solution. By including these feasible solutions, we will have an optimal solution.
Assume that you have an objective function that needs to be optimized (either maximized or minimized) at a given point. It makes greedy choices at each stage to ensure that the objective function is optimized. The greedy method has only one shot to compute the optimal solution so that it never goes back and reverses the decision. Basically, a problem must comprise these two components for a greedy method to work:
Optimal substructure: The optimal solution for the problem contains optimal solutions to the sub-problems.
Greedy choice property: If you make a choice that seems the best at the moment and solves the remaining sub-problems later, you still reach an optimal solution. You will never have to reconsider your earlier choices.
Let's see the general method of the greedy method:
if n = 5 and a = [a1,a2,a3,a4,a5]
Greedy(a, n)
{
for (i = 1; i < n; i++) {
//select an input and call it x
x = select(a);
// if it is feasible it is included in solution
if feasible(x) {
solution = solution + x;
}
}
}
Sometimes, greedy methods fail to find the globally optimal solution because they do not consider all the data. The choice made by a greedy algorithm may depend on choices it has made so far, but it is not aware of future choices it could make.
Optimal SubStructure
A problem is said to have optimal substructure if an optimal solution can be constructed efficiently from optimal solutions of its subproblems. For example, the Shortest Path problem has the following optimal substructure property. If a node, x, lies in the shortest path from a source node, u, to the destination node, v, then the shortest path from u to v is a combination of the shortest path from u to x and the shortest path from x to v. The standard All Pair Shortest Path algorithms like Floyd–Warshall and Bellman-Ford are typical examples of Dynamic Programming.
On the other hand, the Longest Path problem doesn’t have the Optimal Substructure property. Here, by Longest Path, we mean the longest simple path (path without cycle) between two nodes. Consider the following unweighted graph given in the CLRS book.
There are two longest paths from q to t: q→r→t and q→s→t. Unlike the shortest paths, these longest paths do not have the optimal substructure property. For example, the longest path q→r→t is not a combination of the longest path from q to r and longest path from r to t because the longest path from q to r is q→s→t→r, and the longest path from r to t is r→q→s→t.
Recurrence Relation
A recurrence relation describes a sequence of numbers. Early terms are specified explicitly, and later terms are expressed as a function of their predecessors. We have two common ways to solve recurrence relationship problems. The first one is the back substitution method, and the second is the Tree method. Back substitution can be used to come up with a formula for some of the simpler recurrence relations.
A back substitution starts with the recurrence relation. Then, we substitute in a similar expression or whichever of the functions occur in the expression. Then, you substitute again and again until you can see a pattern that takes you all the way down to the end or other simple cases, where a number answer is directly known from the initial conditions. The back substitution method is useful for solving a linear system of equations.
The tree method is useful for visualizing what happens when a recurrence is iterated. It diagrams the tree of recursive calls and the amount of work done at each call. The depth of the tree, in this case, does not really matter; the amount of work at each level is decreasing so quickly that the total is only a constant factor more than the root. Recursion trees can be useful for gaining intuition about the closed form of a recurrence, but they are not proof.
Dynamic Programming
In general, Dynamic programming (DP) is an algorithm design technique that follows the Principle of Optimality. The Principal of Optimality says that a problem can be solved by taking seek and soft decisions. In fact, it is a kind of careful brute force. The basic idea of dynamic programming is to take a problem and split it into subproblems (Divide and conquer), solve those subproblems, and reuse the result of them to find the solution. There are two uses for dynamic programming:
Finding an optimal solution: We want to find a solution that is as large as possible or as small as possible.
Counting the number of solutions: We want to calculate the total number of possible solutions.
Let's see how dynamic programming is applicable with an example: In this problem that we'll call knapsack I/O, we will have m as bag capacity and n as the number of objects in the bag. Each object has a weight and profit. We cannot put all the objects in the bag, but we want to put objects that have maximum profit and minimum weights.
The result should be X={x1, x2, x3, x4}, which shows which objects are or aren't included, like X={1,0,0,1}. Each x can be zero/one but not fractions. In fact, objects are not divisible or fractional. They are solid. Either carry it or don't carry it. The goal is finding Σmax(pixi) and Σwixi <= m.
Now, let's check if we can use dynamic programming to solve this problem or not. Because the problem asked for a maximum result, it is an optimization problem, so we can use dynamic programming for it. Also, in dynamic programming, problems should be solved in a sequence of decisions. For each object, we can make a decision to include it or not.
Also, in dynamic programming, we should try all possible solutions and pick up the best one. In our example, we can have lots of solutions, such as: x = {0, 0, 0, 0} , x= {1, 1, 1, 1} , x= {0, 0, 0, 1} , x= {1, 0, 0, 0} , x= {1, 1, 0, 0}, and, for this example, we can find 2n different choices.
Let's solve it using the tabulation method. We will add values one-by-one in the table, and we start with 0, 0. At the first check, there is no profit. In fact, its profit is zero, so we cannot pick any object because we are looking for objects with max profit. We fill the row with 0, exactly like below:
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|||
Pi |
Wi |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
2 |
1 |
0 |
||||||||
2 |
3 |
2 |
0 |
||||||||
5 |
4 |
3 |
0 |
||||||||
6 |
5 |
4 |
0 |
Also, for the first columns, we add zero because columns indicate weights, and when weight is zero, we would not have any options. Next, we only consider the first object and ignore all of them. In dynamic programming, it is very important that do not even think to the rest of the rows and totally ignore them. like:
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|||
Pi |
Wi |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
2 |
1 |
0 |
* |
|||||||
2 |
3 |
2 |
0 |
||||||||
5 |
4 |
3 |
0 |
||||||||
6 |
5 |
4 |
0 |
In the table above, we only consider reds and try to find a right value for red * and think of our table as a smaller table, meaning that whenever we are in ith row, we only consider all objects in previous rows:
0 |
1 |
|||
Pi |
Wi |
0 |
0 |
0 |
1 |
2 |
1 |
0 |
* |
For the first row, the weight of the first object is 2. So, it can only be filled when bag capacity is 2 or greater, and we just add relative profit in the cell. Also, the rows before 2 get an exact copy of the maximum value of current column of the upper row or current row's previous column value:
0 |
1 |
2 |
|||
Pi |
Wi |
0 |
0 |
0 |
0 |
1 |
2 |
1 |
0 |
0 |
1 |
For the rest of the columns in the first row, we can add only 1 because we only have one object even if we have more empty space. See the table below:
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|||
Pi |
Wi |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
2 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
2 |
3 |
2 |
0 |
||||||||
5 |
4 |
3 |
0 |
||||||||
6 |
5 |
4 |
0 |
Let's fill the second row. For the second row, as I mentioned before, we must include the first object. The weight of second object 3, meaning that it can only be filled when its capacity is 3. For cells of columns before it, we add upper rows or rows before value which is maximum.
For column 4 row 2, we fill it with 2 because 2, the value of the previous column of the same row, is bigger than 1, the value of same column's upper row. For other cells in the row after the third column, we need to consider rows before it. That means we have to find the total weight of the previous rows, like 3 + 2 = 5 and check if the cell's capacity that we want to fill is less than equal to the sum or not. if yes, then we add new profit to related cells like so:
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|||
Pi |
Wi |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
2 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
2 |
3 |
2 |
0 |
0 |
1 |
2 |
2 |
3 |
3 |
3 |
3 |
We can continue like this to fill all cells of the table. The final result will be a table like:
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|||
Pi |
Wi |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
2 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
2 |
3 |
2 |
0 |
0 |
1 |
2 |
2 |
3 |
3 |
3 |
3 |
5 |
4 |
3 |
0 |
0 |
1 |
2 |
5 |
5 |
6 |
7 |
7 |
6 |
5 |
4 |
0 |
0 |
1 |
2 |
5 |
6 |
6 |
7 |
8 |
In order to understand it better, I will write the formula: V[i,w] = max{v[i-1,w], v[i-1, w-w[i]]+Pi}
Let's see the formula in action; if I want to fill V[4, 1] it will be V[4, 1] = max{V[3, 1], V[3,1-5]+6} => 0
The maximum result we get from this method is 8. It is on the last row. We check if 8 is repeated in other rows or not. If not, then we get its row number; in our example 8 is in the 4th row, so the 4th x will be one, and the profit of 4th object is 6. We subtract the profit of object from weight of object 6-4= 2, so we check if 2 is in one row or in multiple rows. 2 is in three rows, so we pick up the first row that contains 2. The row number is 2, and we make the second x 1. Then, we check for 0, which is 0. The result will be X={0,1,0,1}.
Final dynamic programming implementation in pseudocode:
main()
{
int P[5] = {0,1,2,5,6};
int wt[5] = {0,2,3,4,5};
int m = 8 , n ;
int k[5][9];
for (int i = 0 ; i <= n; i++) {
for (int w = 0; w <= m; w++) {
if (i == 0 || w == 0)
k[i][w];
else if (wt[i] <= w)
k[i][w]= max(P[i]+k[i-1][w-wt[i]], k[i-1][w]);
else
k[i][w] = k[i-1][w];
}
}
cout << k[n][w];
}
If you wonder how to excel in Dynamic programming, I would say the only way is to solve lots of problems!
Further Reading
Opinions expressed by DZone contributors are their own.
Comments