Dynamic Programming has similarities with backtracking and divide-conquer in many respects. Here is how we generally solve a problem using dynamic programming.

1. Split the problem into overlapping sub-problems.
2. Solve each sub-problem recursively.
3. Combine the solutions to sub-problems into a solution for the given problem.
4. Don’t compute the answer to the same problem more than once.

Let us see some problems in which we can implement the above procedure.

1. The Fibonacci Sequence (http://en.wikipedia.org/wiki/Fibonacci_number)

Let us devise a program to calculate nth Fibonacci number.

Let us solve this recursively.

int fibo(int n)
{
    if(n<=2)
        return 1;

    else 
        return fibo(n-2)+fibo(n-1);
}

The complexity of the above program would be exponential

Now let are solve this problem dynamically.

int memory[500]
memset(memory, -1 ,500)
int fibo(int n) {
if(n<=2) 
    return 1;

if(memory[n]!=-1)   
    return memory[n];

int s=fibo(n-1)+fibo(n-2);
memory[n]=s;
return s;
}

We have n possible inputs to the function: 1, 2, …, n. Each input will either:–

1. be computed, and the result saved

2. be returned from the memory

Each input will be computed at most once Time complexity is O(n × k), where k is the time complexity of computing an input if we assume that the recursive calls are returned directly from memory(O(1))

Since we’re only doing constant amount of work tocompute the answer to an input, k = O(1)

Total time complexity is O(n).