Basic analysis of Dynamic Programming.

Dynamic Programming (DP) is a simple technique but it can be difficult to master. One easy way to identify and solve DP problems is by solving as many problems as possible. The term Programming is not related to coding but it is from literature, and means filling tables (similar to Linear Programming).

Dynamic programming and memorization work together. The main difference between dynamic programming and divide and conquer is that in the case of the latter, sub problems are independent, whereas in DP there can be an overlap of sub problems. By using memorization [maintaining a table of sub problems already solved], dynamic programming reduces the exponential complexity to polynomial complexity (O(n2), O(n3), etc.) for many problems.

The major components of DP are:

1. Recursion: Solves sub problems recursively.
2. Memorization: Stores already computed values in table (Memorization means caching).

Dynamic Programming = Recursion + Memorization

Properties of Dynamic Programming-

The two dynamic programming properties which can tell whether it can solve the given problem or not are:

1. Optimal substructure: an optimal solution to a problem contains optimal solutions to sub problems.
2. Overlapping sub problems: a recursive solution contains a small number of distinct sub problems repeated many times.

NOTE: Like Greedy and Divide and Conquer techniques, DP cannot solve every problem. There are problems which cannot be solved by any algorithmic technique [Greedy, Divide and Conquer and Dynamic Programming].

The difference between Dynamic Programming and straightforward recursion is in memorization of recursive calls. If the sub problems are independent and there is no repetition then memorization does not help, so dynamic programming is not a solution for all problems.

Dynamic Programming Approaches-

Basically there are two approaches for solving DP problems:

1. Bottom-up dynamic programming
2. Top-down dynamic programming

Bottom-up Dynamic Programming :

In this method, we evaluate the function starting with the smallest possible input argument value and then we step through possible values, slowly increasing the input argument value. While computing the values we store all computed values in a table (memory). As larger arguments are evaluated, pre-computed values for smaller arguments can be used.

Top-down Dynamic Programming :

In this method, the problem is broken into sub problems; each of these sub problems is solved; and the solutions remembered, in case they need to be solved. Also, we save each computed value as the final action of the recursive function, and as the first action we check if pre-computed value exists.

Bottom-up v/s Top-down Programming-

In bottom-up programming, the programmer has to select values to calculate and decide the order of calculation. In this case, all sub problems that might be needed are solved in advance and then used to build up solutions to larger problems. In top-down programming, the recursive structure of the original code is preserved, but unnecessary recalculation is avoided. The problem is broken into sub problems, these sub problems are solved and the solutions remembered, in case they need to be solved again.

Examples of Dynamic Programming Algorithms-

• Many string algorithms including longest common subsequence, longest increasing subsequence, longest common substring, edit distance.
• Algorithms on graphs can be solved efficiently: Bellman-Ford algorithm for finding the shortest distance in a graph, Floyd’s All-Pairs shortest path algorithm, etc.
• Chain matrix multiplication
• Subset Sum
• 0/1 Knapsack
• Travelling salesman problem, and many more

Example :

1. Fibonacci Series-

In Fibonacci series, the current number is the sum of previous two numbers. The Fibonacci series is defined as follows:

Fib(n) = 0 ------------------------> for n=0
       = 1 ------------------------> for n=1
       = Fib(n-1) + Fib(n-2) -----> for n > 1

The recursive implementation can be given as:

int RecursiveFib (int n) 
{
    if(n == 0) return 0;
    if (n ==1 ) return 1;
    return RecursiveFib (n - 1) + RecursiveFib (n - 2);
}

How does Memorization help?

Calling fib(5) produces a call tree that calls the function on the same value many 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))

In the above example, fib(2) was calculated three times (overlapping of subproblems). If n is big, then many more values of fib (sub problems) are recalculated, which leads to an exponential time algorithm. Instead of solving the same sub problems again and again we can store the previous calculated values and reduce the complexity.

Memorization works like this: Start with a recursive function and add a table that maps the function’s parameter values to the results computed by the function. Then if this function is called twice with the same parameters, we simply look up the answer in the table.

Improving: Now, we see how DP reduces this problem complexity from exponential to polynomial. As discussed earlier, there are two ways of doing this. One approach is bottom-up: these methods start with lower values of input and keep building the solutions for higher values.

int fib[n];
int fib (int n) 
{
    //Checking base cases
    if (n ==0 || n == 1) return 1;
    fib[0] = 1;
    fib[1] = 1;
    for (int i=2 ; i <n ; i++)
        fib[i] = fib[i-1] + fib[i-2];
    return fib[n-1];
}

The other approach is top-down. In this method, we preserve the recursive calls and use the values if they are already computed. The implementation for this is given as:

int fib[n];
int fibonacci (int n) 
{
   if (n == 1) 
      return 1;
   if (n == 1) 
      return 1;
   if (fib[n] != 0) 
      return fib[n];
   return fib[n] = fibonacci (n-1) + fibonacci (n-2);
}

Note: For all problems, it may not be possible to find both top-down and bottom-up programming solutions.

Both versions of the Fibonacci series implementations clearly reduce the problem complexity to O(n). This is because if a value is already computed then we are not calling the subproblems again. Instead, we are directly taking its value from the table.

Time Complexity: O(n).

Space Complexity: O(n), for table.

Further Improving: One more observation from the Fibonacci series is: The current value is the sum of the previous two calculations only. This indicates that we don’t have to store all the previous values. Instead, if we store just the last two values, we can calculate the current value.

The implementation for this is given below:

int fibonacci (int n) 
{
    int a = 0 , b = 1 , sum , i;
    for (i = 2 ; i < n ; i++) {
        sum = a+b;
        a = b;
        b = sum;
    }
    return sum;
}

Time Complexity: O(n).

Space Complexity: O(1).

Note: This method may not be applicable (available) for all problems.

Observations- While solving the problems using DP, try to figure out the following:

1. See how the problems are defined in terms of subproblems recursively.
2. See if we can use some table [memorization] to avoid the repeated calculations.