Dynamic programming

Optional Reading: Chapter 17

One important algorithmic technique is dynamic programming.

Looking at problems upside-down can help!

(But be careful with your hat!)

Dynamic programming

Two steps to formulating a dynamic programming algorithm:

Find a recursive solution that involves solving the same problems many times.
Calculate bottom up to avoid recalculation.

Fibonacci numbers

1 1 2 3 5 8 13 21 34 44 89 ...

Fact: Fibonacci(n) is approximately 1.618ⁿ⁺¹ / sqrt(5) (where 1.618 = (1 + sqrt(5) / 2)).

The golden ratio!

Algorithm Fibonacci(n)
if n <= 1, then:
  return 1
else:
  return Fibonacci(n - 1) + Fibonacci(n - 2)
end of if

A call tree:

        5
      /   \
    4       3
   / \     / \
  3   2    2 1
 / \ / \  / \
 2 1 1 0  1 0
/ \
1 0

This takes O(1.618ⁿ) time!

 to compute     takes
Fibonacci(40)  75.22 seconds
Fibonacci(70)   4.43 years

The dynamic programming approach

Dynamic programming suggests we start at the bottom and work up.

Algorithm Fast-Fibonacci(n)
Let fib[0] and fib[1] be 1.
for each i from 2 to n, do:
  Let fib[i] be fib[i - 2] + fib[i - 1].
end of loop
return fib[n].

The number of additions now is only n-1!

  to compute     took        now takes
Fibonacci(40)   75.22 sec    2 microseconds
Fibonacci(70)    4.43 years  3 microseconds

Making change

Problem MakeChange:
Input: coin denominations d[0], d[1],..., d[n-1], an amount a
Output: the number of coins needed to total a exactly.

Consider Freedonia: we have pennies, 4-cent pieces, and nickels; and we have a=8. The output should be 2 (since we could use two four-cent pieces), even though the greedy method would output 4 (a nickel and three pennies).

Formulating a solution

Think of a recursive solution:

  MakeChange(a) = 1 +      min    MakeChange(a - d[i])
                       0 <= i < n

Compute bottom up

Algorithm DynamicMakeChange(amt, d[0], d[1],..., d[n-1]):
Let coins[0] be 0.
for each a from 1 to amt, do:
  coins[a] <- infinity // an upper bound
  for each j from 0 to n - 1, do:
    if d[j] <= a and 1 + coins[a - d[j]] < coins[a], then:
      Let coins[a] be 1 + coins[a - d[j]].
    end of if
  end of loop
end of loop
return coins[amt].

With our earlier example, coins would look like

+---+---+---+---+---+---+---+---+---+
| 0 | 1 | 2 | 3 | 1 | 1 | 2 | 3 | 2 |
+---+---+---+---+---+---+---+---+---+

This algorithm takes O(amt * n) time.

Graph paths

Problem AllPairsPaths:
Input: graph (V, E) with edge distances d : E -> positive reals.
Output: length p[s,t] of shortest path from s to t, for all pairs of vertices.

Example problem:

       1
    B --- E
    | \   |
   3| 6\  | 1
    |   \ |
    A --- S
       2

Output:

A recursive approach

Define p[s,t]^(k) as the shortest path between s and t, passing only through vertices 1,2,...,k in between. (The superscripts do not indicate exponentiation; they are just another index.)

We can calculate p[s, t]^(k) in terms of the p^(k - 1):

  p[s, t]^(k) = min { p[s, t]^(k - 1), p[s, k]^(k - 1) + p[k, t]^(k - 1) }

since any shortest path never goes through vertex k more than once.

The pseudocode

Let n be the number of vertices.

Algorithm DynamicPaths(d):
for each s from 1 to n, do:
  for each t from 1 to n, do:
    Let p[s, t]^(0) be d(s, t).
  end of loop
end of loop
for each k from 1 to n, do:
  for each s from 1 to n, do:
    for each t from 1 to n, do:
      Let p[s, t]^(k) be min { p[s, t]^(k - 1), p[s, k]^(k - 1) + p[k, t]^(k - 1) }.
    end of loop
  end of loop
end of loop
return p^(n).

Example (using # to represent infinity):

      0 3 2 #
p^(0) 3 0 6 1
      2 6 0 1
      # 1 1 0

      0 3 2 #
p^(1) 3 0 5 1
      2 5 0 1
      # 1 1 0

      0 3 2 4
p^(2) 3 0 5 1
      2 5 0 1
      4 1 1 0

      0 3 2 3
p^(3) 3 0 5 1
      2 5 0 1
      3 1 1 0

      0 3 2 3
p^(4) 3 0 2 1
      2 2 0 1
      3 1 1 0

This algorithm takes O(n³) time.