Dynamic Programming Examples
Building from the bottom up
Dynamic Programming
The solution to a certain class of problems involves solving the same subproblems repeatedly.
Example: Consider the fibonacci numbers. The definition for the nth fibonacci number is the following:
fibo(n) = fibo(n-1) + fibo(n+2); fibo(0) = 1, fibo(1) = 1
The most obvious approach to writing a program to solve for fibo(n) is to write a recursive program that directly implements the definition. Consider, though, what happens when the program is executed for fibo(5). fibo(5) requires the solution to fibo(4) and fibo(3). fibo(4) requires the solution to fibo(3) and fibo(2). fibo(3) requires the solution of fibo(2) and fibo(1). This direct approach requires us to solve subproblems like fibo(3) or fibo(2) several times each.
There are two obvious improvements to this approach.
1. Keep the same general approach but the first time a subproblem is solved save the solution to it so subsequent requests for solutions to subproblems should first determine if the subproblem has already been solved and saved. If already solved the new approach would simply look up and return the answer rather than use recursive calls to compute it repeatedly.
2. Restructure the problem so that we solve the smallest instances of the problem first and gradually build up to a solution to the stated problem. For example, fibo(1) + fibo(0) gives fibo(2) and fibo(2) + fibo(1) gives fibo(3), etc.
Both of the above solutions turn an exponential algorithm into a linear one - a substantial reduction.
The first linear approach listed above (1.) is not considered to be pure dynamic programming. This approach is sometimes referred to as memoization; perhaps because we keep a memo of the answer for each subproblem solved. Although not identical, the two methods are very similar.
Another Example:
Consider a sequence of n numbers, A = {a1, a2, a3, ..., an}. A subsequence of a given sequence is just the given sequence with 0 or more of the elements removed.
Let's find an algorithm that finds the subsequence, A' = {ai1, ai2, ai3, ...aik} of A that maximizes ai1 - ai2 + ai3 - ... +- aik (i.e. the sign alternates).
We may accomplish this by beginning at the right of the original sequence and keeping track of the greatest and least alternating sums as we proceed to the left. Performing the algorithm using sample data probably illustrates the principle best.
Let A = {5, 3, 2, 1, 3, 6}.
If we begin at the last element on the right then the largest alternating sum from that point forward is simply 6. The least is obtained by leaving 6 out and simply having the sum = 0. In order to proceed to the left (ultimately reaching the start of the sequence) we need to keep our computations in a table. Here is what we have so far.
| Greatest | - | - | - | - | - | 6 |
| Prev Index | - | - | - | - | - | - |
| Least | - | - | - | - | - | 0 |
| Prev Index | - | - | - | - | - | - |
| Value | 5 | 3 | 2 | 1 | 3 | 6 |
| Index | 5 | 4 | 3 | 2 | 1 | 0 |
Next we move to position 1 and determine how to obtain the alternating sequences with the greatest and least sums. If we decide to use the number in position 1 then we have two choices.
1. We can leave out position 0. This yields an alternating sum of 3. This does not better our previous Max of 6 so it is of no use.
2. We can include position 0. This yields an alternating sum of 3 - 6 = -3. This does better our previous Min of 0 so we now have a new Min.
Perhaps it is now clear that we need to store the values and indices of our current Max and Min.
| Greatest | - | - | - | - | 3 | 6 |
| Prev Index | - | - | - | - | - | - |
| Least | - | - | - | - | -3 | 0 |
| Prev Index | - | - | - | - | 0 | - |
| Value | 5 | 3 | 2 | 1 | 3 | 6 |
| Index | 5 | 4 | 3 | 2 | 1 | 0 |
| Max | 6 |
| Max Index | 0 |
| Min | -3 |
| Min Index | 1 |
Next we move to position 2 and recompute. You may have deduced by now that one achieves the greatest alternating sum at any position by subtracting the Min so far and one achieves the least alternating sum for a position by subtracting the Max so far. So for position 2 we obtain
Greatest is 1 - -3 = 4 (no new Max)
Least is 1 - 6 = -5 (a new Min)
| Greatest | - | - | - | 4 | 3 | 6 |
| Prev Index | - | - | - | 1 | - | - |
| Least | - | - | - | -5 | -3 | 0 |
| Prev Index | - | - | - | 0 | 0 | - |
| Value | 5 | 3 | 2 | 1 | 3 | 6 |
| Index | 5 | 4 | 3 | 2 | 1 | 0 |
| Max | 6 |
| Max Index | 0 |
| Min | -5 |
| Min Index | 2 |
Proceeding in a similar manner we have for position 3
Greatest is 2 - -5 = 7 (a new Max)
Least is 2 - 6 = -4 (no new Min)
| Greatest | - | - | 7 | 4 | 3 | 6 |
| Prev Index | - | - | 2 | 1 | - | - |
| Least | - | - | -4 | -5 | -3 | 0 |
| Prev Index | - | - | 0 | 0 | 0 | - |
| Value | 5 | 3 | 2 | 1 | 3 | 6 |
| Index | 5 | 4 | 3 | 2 | 1 | 0 |
| Max | 7 |
| Max Index | 3 |
| Min | -5 |
| Min Index | 2 |
Proceeding in a similar manner we have for position 4
Greatest is 3 - -5 = 8 (a new Max)
Least is 3 - 7 = -4 (no new Min)
| Greatest | - | 8 | 7 | 4 | 3 | 6 |
| Prev Index | - | 2 | 2 | 1 | - | - |
| Least | - | -4 | -4 | -5 | -3 | 0 |
| Prev Index | - | 3 | 0 | 0 | 0 | - |
| Value | 5 | 3 | 2 | 1 | 3 | 6 |
| Index | 5 | 4 | 3 | 2 | 1 | 0 |
| Max | 8 |
| Max Index | 4 |
| Min | -5 |
| Min Index | 2 |
Proceeding in a similar manner we have for position 5
Greatest is 5 - -5 = 10 (a new Max)
Least is 5 - 8 = -3 (no new Min)
This finally yields
| Greatest | 10 | 8 | 7 | 4 | 3 | 6 |
| Prev Index | 2 | 2 | 2 | 1 | - | - |
| Least | -3 | -4 | -4 | -5 | -3 | 0 |
| Prev Index | 4 | 3 | 0 | 0 | 0 | - |
| Value | 5 | 3 | 2 | 1 | 3 | 6 |
| Index | 5 | 4 | 3 | 2 | 1 | 0 |
| Max | 10 |
| Max Index | 5 |
| Min | -5 |
| Min Index | 2 |
And we discover that the subsequence {5, 1, 6} maximizes the alternating sum.
{5, 1, 6} yields 5 - 1 + 6 = 10
Top of this page 
Home page 
