Dynamic Programming

Dynamic Programming
—Those who cannot remember the past are doomed to repeat it. George Santayana.

I have seen the dictum on the lecture notes from Jeff Erickson on Dynamic Programming (DP). I would like to start my notes on DP with it too!

The basic idea of DP is drawn from the ituition behind divide and conquer and is the opposite of the greedy strategy (If a problem is solved by the greedy strategy correctly, it is all about luck, and usually this is very rare). DP implicitly explores the space of all possible solutions, by carefully decomposing things into a serious of subproblems, and then building up correct solutions to larger and larger subproblems. It is systematically working through the exponentially large set of possible solutions to the problem; however it does this without ever examining all of them explicitly. Therefore, DP is operating dangerously close to the edge of brute-forth search. The trick part is how to avoid examining all the possibilities.

Two difficult parts to understand dynamic programming are one that, how to avoid examining all the possibilities, and the other, memoization or iteratation. These two are essentially the principles of DP: memoization or iteratation over subproblems. memoizationand iteration are corresponding to top-down approach and bottom-up approach respectively to solve the problem.

The first part is tricky. It is about finding recursive subproblems and I really feel that it needs experience or hard work to be able to identify quickly. However for the second part (implementation part/coding part), it can be readily learned.

To appreciate memorization, we look at the example of Fibonacci Numbers. Because the recursive subproblems are already given!

int Fib(int n)
{
	if(n<2)
		return n;
	else
		return Fib(n-1)+Fib(n-2);
}

Consider its running time, consider T(n) represents the number of recursive calls to Fib, we have the recurrences
T(0)=1, T(1)=1, T(n)=T(n-1)+T(n-2)+1
It grows as Fibonacci Numbers, which increase exponentially. Thus we have not achieved a polynomial-time solution.

As a specific example, if we call, say, Fib(5), we produce a call tree that calls the function on the same value many different times:
Fib(5)
Fib(4) + Fib(3)
(Fib(3) + Fib(2)) + (Fib(2) + Fib(1))
((Fib(2) + Fib(1)) + (Fib(1) + Fib(0))) + ((Fib(1) + Fib(0)) + Fib(1))
(((Fib(1) + Fib(0)) + Fib(1)) + (Fib(1) + Fib(0))) + ((Fib(1) + Fib(0)) + Fib(1))
We also observe that our recursive algorithm Fib(n) is really only solving n+1 different subproblems: Fib(0) to Fib(n). The fact that it runs in exponential time as written is simply due to the spectacular redundancy in the number of times it issues each of these calls. How to eliminate all this redundancy?

Memorize the value of Fib(n) in a globally accessible place first time we compute it!
This technique of saving values that have already been calculated is called memoization; this is the top-down approach, since we first break the problem into subproblems and then calculate and store values.

int result[n+1]={-1};
int top_down_Fib(int n)
{
	if(n<2)
	{   		
		result[n]=n;
		return n;
	}
	else
	{
		result[n]=top_down_Fib(n-1)+top_down_Fib(n-2);
		return result[n];
	}
}

Then how to iterate? In the bottom-up approach we calculate the smaller values of Fib first, then build larger values from them. This method also uses O(n) time since it contains a loop that repeats n ? 1 times, however it only takes constant (O(1)) space, in contrast to the top-down approach which requires O(n) space to store the map.

int bottom_up_Fib(int n)
{
	int previous_Fib=0;
	int current_Fib=1;
	int temp;
	if(n<2)
		return n;
	else
		for (int i=2;i<=n;++i)
		{
			temp=previous_Fib+current_Fib;
			previous_Fib=current_Fib;
			current_Fib=temp;
         }
		return current_Fib;
}

Reference:

1.Online notes from Jeff Erickson, http://compgeom.cs.uiuc.edu/~jeffe/teaching/algorithms/
2.Jon Kleinberg and Eva Tardos, Algorithm Design, http://books.google.com/
3.http://en.wikipedia.org/wiki/Dynamic_programming
4.Dynamic Programming Practice Problems, http://people.csail.mit.edu/bdean/6.046/dp/