Dynamic Programming was invented by Richard Bellman, 1950. It is a very general technique for solving optimization problems. Using Dynamic Programming requires that the problem can be divided into overlapping similar sub-problems. A recursive relation between the larger and smaller sub problems is used to fill out a table. The algorithm remembers solutions of the sub-problems and so does not have to recalculate the solutions.
Also optimal problem must have the principle of optimality (phase coined by Bellman) meaning that the optimal problem can be posed as the optimal solution among sub problems. This is not true for all optimal problems.
Dynamic Programming requires:
1. Problem divided into overlapping sub-problems
2. Sub-problem can be represented by a table
2. Principle of optimality, recursive relation between smaller and larger problems
Compared to a brute force recursive algorithm that could run exponential, the dynamic programming algorithm runs typically in quadratic time. (Recall the algorithms for the Fibonacci numbers.) The recursive algorithm ran in exponential time while the iterative algorithm ran in linear time. The space cost does increase, which is typically the size of the table. Frequently, the whole table does not have to store.
Computing binomial coefficients is non optimization problem but can be solved using dynamic programming.
Binomial coefficients are represented by C(n, k) or (nk) and can be used to represent the coefficients of a binomail:
(a + b)n = C(n, 0)an + ... + C(n, k)an-kbk + ... + C(n, n)bn
The recursive relation is defined by the prior power
C(n, k) = C(n-1, k-1) + C(n-1, k) for n > k > 0
IC C(n, 0) = C(n, n) = 1
Dynamic algorithm constructs a nxk table, with the first column and diagonal filled out using the IC.
Construct the table:
|
|
|
|
|
k |
|
|
|
|
|
|
0 |
1 |
2 |
... |
k-1 |
k |
|
|
0 |
1 |
|
|
|
|
|
|
|
1 |
1 |
1 |
|
|
|
|
|
|
2 |
1 |
2 |
1 |
|
|
|
|
n |
. . . |
|
|
|
|
|
|
|
|
k |
1 |
|
|
|
|
1 |
|
|
. . . |
|
|
|
|
|
|
|
|
n-1 |
1 |
|
|
|
C(n-1, k-1) |
|
|
|
n |
1 |
|
|
|
|
C(n, k) |
The table is then filled out iteratively, row by row using the recursive relation.
Algorithm Binomial(n, k)
for i ← 0 to n do // fill out the table row wise
for i = 0 to min(i, k) do
if j==0 or j==i then C[i, j] ← 1 // IC
else C[i, j] ← C[i-1, j-1] + C[i-1, j] // recursive relation
return C[n, k]
The cost of the algorithm is filing out the table. Addition is the basic operation. Because k ≤ n, the sum needs to be split into two parts because only the half the table needs to be filled out for i < k and remaining part of the table is filled out across the entire row.
A(n, k) = sum for upper triangle + sum for the lower rectangle
= ∑i=1k ∑j=1i-1 1 + ∑i=1n ∑j=1k 1
= ∑i=1k (i-1) + ∑i=1n k
= (k-1)k/2 + k(n-k) ε Θ(nk)
Note we do not need to keep the whole table, only the prior row.
We'll consider more sophisticate dynamic programming problems, Warshall's and Floyd's algorithms.