Transcript Dynamic Programming

Analysis of Algorithms
Dynamic Programming
Dynamic Programming
A dynamic programming algorithm solves every sub
problem just once and then
Saves its answer in a table (array), there by
Avoiding the work of recomputing the answer every
time the sub problem is encountered.
Dynamic programming is typically applied to
optimization problems.
What is an optimization problem?
There can be may possible solutions.
Each solution has a value and
We wish to find a solution with the optimal (minimum or
maximum) value
Toward Dynamic Programming
Problems with divide and conquer
Recursive Fibonnacci numbers algorithm with
exponential complexity.
When sub problems are not independent
Fib1(N)
{ if (N =< 1)
return 1;
else
return Fib(N-1) + Fib(N-2)
}
Dynamic Programming
Bottom-up approach with
Memoization


Instead of computing again and again, we can store the computed
results in an array. The stored values can be used for any future
use.
Assume, we want to compute Fib(n) with max. value of n is
MAXVALUE.
#define MAXVALUE 100;
Fib2(n)
{
int F[MAXVALUE];
for(i = 1; i <= n; i++)
F[i] = 1;
for(i = 2; i <= n; i++)
F[i] = F[i-1] + F[i-2];
return F[n];
}
Dynamic Programming
Bottom-up Approach with
Memoization
Sometimes after developing an algorithm using
array , we are able to revise the algorithm to
save originally allocated space
Fib2(n)
{ int Fn = 1, Fn1 = 1, Fn2 = 1;
for(I = 2; I <= n; I++)
{ Fn = Fn1 + Fn2;
Fn2 = Fn1;
Fn1 = Fn;
}
return Fn;
}
Dynamic Programming
The steps in development of dynamic
programming algorithm are
Establish a recursive property that gives the
solution to an instance of a problem
Solve an instance of the problem in Bottomup fashion by solving smaller instances first.
Example of Binomial
Coefficient
The binomial coefficient is given by
n 
n!
k   k!(n  k )! for 0  k  n.
 
For values of n and k that are not small,
We can not compute the binomial
coefficient directly from this definition
because n! is very large
Example of Binomial
Coefficient
We can eliminate the need to compute n!
or k! by using following recursive
property.
n  1 n  1

0kn
n  


k   k  1 k 
  
k  0 or k  n
1
This suggests the following divide-andconquer algorithm.
Example of Binomial
Coefficient Using Divide-andConquer
Int bin(int n, int k)
{
if (k = 0 or n = k )
return 1;
else
return(bin(n-1, k-1) + bin(n-1, k))
}
Example of Binomial
Coefficient Using Divide-andConquer
This algorithm is very similar to the
divide-and-conquer algorithm of
computing nth fabnacci term.
Therefore this algorithm is very
inefficient due to the same reasons.
Example of Binomial
Coefficient Using Dynamic
Programming
We will use the recursive definition to
construct our solution in an array B.
Where B[i, j] will contain i 
 j
 
Solve an instance of the problem in a
bottom-up fashion by computing the rows
in B in sequence starting with the first
row.
`
Int bin(int n, int k)
{
int i, j;
int B[0..n, 0..k];
for i = 0 to n
for j = 0 to minimum(i, k)
if( j = 0 or j = i)
B[i, j] = 1;
else
B[i, j] = B[i-1, j-1] + B[i-1, j];
return B[n, k]
}
Complexity Analysis
number of passes
i 0
1
2
3
k
k+1
j 1
2
3
4
k+1 k+1
total number of passes
1+2+3++k+k+1+k+1…….+k+1
(k+1 is repeacted for n-k+1 times)
k(k+1)/2+(k+1)(n-k+1)
=((2n-k+2)(k+1))/2 є Ө(nk)
n
k+1
Dynamic Programming
Dynamic programming is similar to
divide and conquer in that we find a
recursive property.
But instead of blindly using recursion, we
use the recursive property to iteratively
solve the instances in sequence starting
with the smallest instance
And we solve each instance ONCE