# Class 36: Dynamic Programming (1)

Held: Friday, April 7, 2006

Summary: Today we consider dynamic programming, an algorithm design technique that can significantly improve the running time of very slow algorithms.

Related Pages:

Assignments

Notes:

• The exam took much longer than I intended to prepare, so today's outline is mostly blank.

Overview:

• Multiply-recursive algorithms.
• The Fibonacci Numbers.
• Improving computation with dynamic programming.
• Another example: Efficient computation of prices.

## Multiply Recursive Procedures

• f(x) = g(f(x-1), f(x-1))
• Running time?
• Why?

## Example: The Fibonacci Sequence

• We'll continue by looking at a procedure used to compute the Fibonacci sequence.
• In case you've forgotten (or don't know), the sequence has the form 0 1 1 2 3 5 8 13 21 ...
• That is, each number (except the first two) is the sum of the previous two numbers.
• Why is this an interesting sequence?

### A Recursive Implementation

• We can, of course, write a recursive solution to computing the nth Fibonacci number.
```  public long fib(int n) {
if (n < 2)
return n;
else
return fib(n-1) + fib(n-2);
} // fib(int)
```
• It's short, it's elegant. it's recursive. What's not to like?
• Well, let's consider the efficiency.
• In effect, we do two recursive calls for each call and we don't shrink the parameter much.

### Improving the Recursive Implementation

• Can we make this recursive implementation better? Certainly.
• In particular, We can use arrays to improve the running time of our recursive Fibonacci algorithm.
• How? The biggest problem with the recursive Fibonacci is that we recompute values again and again.
• If we cache (remember) results after we compute them, we can check the cache before repeating a recursive call.
```   public long fibra(int n)
{
// Build a cache, use -1 for "I don't know."
int cache = new long[n+1];
cache[0] = 0;
cache[1] = 1;
for (int i = 2; i <= n; i++)
cache[i] = -1;
// Compute the nth number using the cache.
fibra_helper(n, cache);
} // fibra(int)

public long fibra_helper(int n, long[] cache)
{
// If the cache contains no value
if (cache[n] == -1)
// Compute it
cache[n] = fibra_helper(n-1, cache)
+ fibra_helper(n-2, cache);
// The cache must now return a value, so
// return it.
return cache[n];
} // fibra_helper
```
• Since each element of the array gets filled in once, this is a much faster algorithm.
• The idea of caching values is often called dynamic programming. It's one of the algorithm design strategies you'll often employ.

### An Iterative Implementation

• Of course, we can also compute the values left-to-right.
• Once we've computed all the values in the array of size n+1, we can easily return the nth Fibonacci number.

## Coin Minimization

• We can use the same technique to minimize the number of coins of unknown denominations that makes the same price.

Disclaimer: I usually create these pages on the fly, which means that I rarely proofread them and they may contain bad grammar and incorrect details. It also means that I tend to update them regularly (see the history for more details). Feel free to contact me with any suggestions for changes.

This document was generated by Siteweaver on Tue May 9 08:31:47 2006.
The source to the document was last modified on Thu Jan 12 14:58:07 2006.
This document may be found at `http://www.cs.grinnell.edu/~rebelsky/Courses/CS152/2006S/Outlines/outline.36.html`.

You may wish to validate this document's HTML ; ; Check with Bobby

Samuel A. Rebelsky, rebelsky@grinnell.edu