Introduction Dynamic programming is a confusing name for a programming technique that dramatically reduces the runtime of algorithms: from exponential to polynomial. The basic idea is to try to avoid solving the same problem or subproblem twice. Here is a problem to demonstrate its power: Given a sequence of as many as 10,000 integers (0 < integer < 100,000), what is the maximum decreasing subsequence? Note that the subsequence does not have to be consecutive. Recursive Descent Solution The obvious approach to solving the problem is recursive descent. One need only find the recurrence and a terminal condition. Consider the following solution: 1 #include 2 long n, sequence[10000]; 3 main () { 4 FILE *in, *out; 5 int i; 6 in = fopen ("input.txt", "r"); 7 out = fopen ("output.txt", "w"); 8 fscanf(in, "%ld", &n); 9 for (i = 0; i < n; i++) fscanf(in, "%ld", &sequence[i]); 10 fprintf (out, "%d\n", check (0, 0, 99999)); 11 exit (0); 12 } 13 check (start, nmatches, smallest) { 14 int better, i, best=nmatches; 15 for (i = start; i < n; i++) { 16 if (sequence[i] < smallest) { 17 better = check (i, nmatches+1, sequence[i]); 18 if (better > best) best = better; 19 } 20 } 21 return best; 22 } Lines 1-9 and and 11-12 are arguably boilerplate. They set up some standard variables and grab the input. The magic is in line 10 and the recursive routine `check'. The `check' routine knows where it should start searching for smaller integers, the length of the longest sequence so far, and the smallest integer so far. At the cost of an extra call, it terminates `automatically' when `start' is no longer within proper range. The `check' routine is simplicity itself. It traverses along the list looking for a smaller integer than the `smallest' so far. If found, `check' calls itself recursively to find more. The problem with the recursive solution is the runtime: N Seconds 60 0.130 70 0.360 80 2.390 90 13.190 Since the particular problem of interest suggests that the maximum length of the sequence might approach six digits, this solution is of limited interest. Starting At The End When solutions don't work by approaching them `forwards' or `from the front', it is often fruitful to approach the problem backward. In this case, that means looking at the end of the sequence first. Additionally, it is often fruitful to trade a bit of storage for execution efficiency. Another program might work from the end of the sequence, keeping track of the longest descending (sub-)sequence so far in an auxiliary variable. Consider the sequence starting at the end, of length 1. Any sequence of length 1 meets all the criteria for a longest sequence. Notate the `bestsofar' array as `1' for this case. Consider the last two elements of the sequence. If the the penultimate number is larger than the last one, then the `bestsofar' is 2 (which is 1 + `bestsofar' for the last number). Otherwise, it's `1'. Consider any element prior to the last two. Any time it's larger than an element closer to the end, its `bestsofar' element becomes at least one larger than that of the smaller element that was found. Upon termination, the largest of the `bestsofar's is the length of the longest descending subsequence. This is fairly clearly an O(N 2) algorithm. Check out its code: 1 #include 2 #define MAXN 10000 3 main () { 4 long num[MAXN], bestsofar[MAXN]; 5 FILE *in, *out; 6 long n, i, j, longest = 0; 7 in = fopen ("input.txt", "r"); 8 out = fopen ("output.txt", "w"); 9 fscanf(in, "%ld", &n); 10 for (i = 0; i < n; i++) fscanf(in, "%ld", &num[i]); 11 bestsofar[n-1] = 1; 12 for (i = n-1-1; i >= 0; i--) { 13 bestsofar[i] = 1; 14 for (j = i+1; j < n; j++) { 15 if (num[j] < num[i] && bestsofar[j] >= bestsofar[i]) { 16 bestsofar[i] = bestsofar[j] + 1; 17 if (bestsofar[i] > longest) longest = bestsofar[i]; 18 } 19 } 20 } 21 fprintf(out, "bestsofar is %d\n", longest); 22 exit(0); 23 } Again, lines 1-10 are boilerplate. Line 11 sets up the end condition. Lines 12-20 run the O(N 2) algorithm in a fairly straightforward way with the `i' loop counting backwards and the `j' loop counting forwards. One line longer then before, the runtime figures show better performance: N Secs 1000 0.080 2000 0.240 3000 0.550 4000 0.950 5000 1.450 6000 2.080 7000 2.990 8000 3.700 9000 4.700 10000 6.330 11000 7.350 The algorithm still runs too slow (for competitions) at N=9000. That inner loop (``search for any smaller number'') begs to have some storage traded for it. A different set of values might best be stored in the auxiliary array. Implement an array `bestrun' whose index is the length of a long subsequence and whose value is the first (and, as it turns out, `best') integer that heads that subsequence. Encountering an integer larger than one of the values in this array means that a new, longer sequence can potentially be created. The new integer might be a new `best head of sequence', or it might not. Consider this sequence: 10 8 9 4 6 3 Scanning from right to left (backward to front), the `bestrun' array has but a single element after encountering the 3: 0:3 Continuing the scan, the `6' is larger than the `3', to the `bestrun' array grows: 0:3 1:6 The `4' is not larger than the `6', though it is larger than the `3', so the `bestrun' array changes: 0:3 1:4 The `9' extends the array: 0:3 1:4 2:9 The `8' changes the array similar to the earlier case with the `4': 0:3 1:4 2:8 The `10' extends the array again: 0:3 1:4 2:8 3:10 and yields the answer: 4 (four elements in the array). Because the `bestrun' array probably grows much less quickly than the length of the processed sequence, this algorithm probabalistically runs much faster than the previous one. In practice, the speedup is large. Here's a coding of this algorithm: 1 #include 2 #define MAXN 200000 3 main () { 4 FILE *in, *out; 5 long num[MAXN], bestrun[MAXN]; 6 long n, i, j, highestrun = 0; 7 in = fopen ("input.txt", "r"); 8 out = fopen ("output.txt", "w"); 9 fscanf(in, "%ld", &n); 10 for (i = 0; i < n; i++) fscanf(in, "%ld", &num[i]); 11 bestrun[0] = num[n-1]; 12 highestrun = 1; 13 for (i = n-1-1; i >= 0; i--) { 14 if (num[i] < bestrun[0]) { 15 bestrun[0] = num[i]; 16 continue; 17 } 18 for (j = highestrun - 1; j >= 0; j--) { 19 if (num[i] > bestrun[j]) { 20 if (j == highestrun - 1 || num[i] < bestrun[j+1]){ 21 bestrun[++j] = num[i]; 22 if (j == highestrun) highestrun++; 23 break; 24 } 25 } 26 } 27 } 28 printf("best is %d\n", highestrun); 29 exit(0); 30 } Again, lines 1-10 are boilerplate. Lines 11-12 are initialization. Lines 14-17 are an optimization for a new `smallest' element. They could have been moved after line 26. Mostly, these lines only effect the `worst' case of the algorithm when the input is sorted `badly'. Lines 18-26 are the meat that searches the bestrun list and contain all the exceptions and tricky cases (bigger than first element? insert in middle? extend the array?). You should try to code this right now - without memorizing it. The speeds are impressive. The table below compares this algorithm with the previous one, showing this algorithm worked for N well into five digits: N orig Improved 1000 0.080 0.030 2000 0.240 0.030 3000 0.550 0.050 4000 0.950 0.060 5000 1.450 0.080 6000 2.080 0.090 7000 2.990 0.110 8000 3.700 0.130 9000 4.700 0.140 10000 6.330 0.160 11000 7.350 0.170 20000 0.290 40000 0.570 60000 0.910 80000 1.290 100000 2.220 Marcin Mika points out that you can simplify this algorithm to this tiny little solution: #include #define SIZE 200000 #define MAX(x,y) ((x)>(y)?(x):(y)) int best[SIZE]; // best[] holds values of the optimal sub-sequence int main (void) { FILE *in = fopen ("input.txt", "r"); FILE *out = fopen ("output.txt", "w"); int i, n, k, x, sol = -1; fscanf (in, "%d", &n); // N = how many integers to read in for (i = 0; i < n; i++) { best[i] = -1; fscanf (in, "%d", &x); for (k = 0; best[k] > x; k++) ; best[k] = x; sol = MAX (sol, k + 1); } printf ("best is %d\n", sol); return 0; } Not to be outdone, Tyler Lu points out: The solutions that currently exist use a linear search to find the appropriate location in the 'bestrun' array to insert an integer. However, because the auxiliary array is sorted, we may use binary search (O(log N)) so that for larger sequences, our runtime is decreased. Here is a solution that modifies the previous code: #include #define SIZE 200000 #define MAX(x,y) ((x)>(y)?(x):(y)) int best[SIZE]; // best[] holds values of the optimal sub-sequence int main (void) { FILE *in = fopen ("input.txt", "r"); int i, n, k, x, sol; int low, high; fscanf (in, "%d", &n); // N = how many integers to read in // read in the first integer fscanf (in, "%d", &best[0]); sol = 1; for (i = 1; i < n; i++) { best[i] = -1; fscanf (in, "%d", &x); if(x >= best[0]) { k = 0; best[0] = x; } else { // use binary search instead low = 0; high = sol-1; for(;;) { k = (int) (low + high) / 2; // go lower in the array if(x > best[k] && x > best[k-1]) { high = k - 1; continue; } // go higher in the array if(x < best[k] && x < best[k+1]) { low = k + 1; continue; } // check if right spot if(x > best[k] && x < best[k-1]) best[k] = x; if(x < best[k] && x > best[k+1]) best[++k] = x; break; } } sol = MAX (sol, k + 1); } printf ("best is %d\n", sol); fclose(in); return 0; } Summary These programs demonstrate the main concept behind dynamic programming: build larger solutions based on previously found solutions. This building-up of solutions often yields programs that run very quickly. For the previous programming challenge, the main subproblem was: Find the largest decreasing subsequence (and its first value) for numbers to the `right' of a given element. Note that this sort of approach solves a class of problems that might be denoted ``one-dimensional''.