Placement Practice | Dynamic Programming - I

In this blog, you will learn what dynamic programming is

Introduction to Dynamic Programming

Dynamic programming technique is similar to the divide and conquer approach. Both solve a problem by breaking it down into several subproblems that can be solved recursively.

• The difference between the two is that in a dynamic programming approach, the results obtained from solving smaller subproblems are reused (by maintaining a table of results) in the calculation of larger subproblems.

• Thus, dynamic programming is a Bottom-up approach that begins by solving the smaller sub-problems, saving these partial results, and then reusing them to solve larger sub-problems until the solution to the original problem is obtained.

• Reusing the results of sub-problems (by maintaining a table of results) is the major advantage of dynamic programming because it avoids the re-computations (computing results twice or more) of the same problem.

• Thus, the Dynamic programming approach takes much less time than naïve or straightforward methods, such as a divide-and-conquer approach that solves problems in the top-down method and having lots of re-computations.

• The dynamic programming approach always gives a guarantee to get an optimal solution.

Take the case of generating the Fibonacci sequence.

We know that n-th Fibonacci number fib(n) can be defined as:

fib(n) = fib(n-1) + fib(n-2), where n >= 2.
and,
fib(0) = 0 
fib(1) = 1

The first few Fibonacci numbers are:

1, 1, 2, 3, 5, 8, 13, 21, 34,...

Recursive program:

int fib(int n) 
{ 
    if (n <= 1) 
        return n; 

    return fib(n-1) + fib(n-2); 
}

The time complexity of the recursive solution is exponential. However, we can improve the time complexity by using Dynamic Programming approach and storing the results of the subproblems as shown below:

int fib(int n) 
{ 
  int f[n+2];   
  int i; 
  
  // 0th and 1st number of the series are 0 and 1
  f[0] = 0; 
  f[1] = 1; 
  
  for (i = 2; i <= n; i++) 
  { 
      f[i] = f[i-1] + f[i-2]; 
  } 
  
  return f[n]; 
} 

The time complexity of the above solution is linear.

---

Properties of a Dynamic Programming Problem

There are two main properties of any problem which can be solved using the dynamic programming approach:

1. Overlapping Subproblem Property

2. Optimal Substructure Property

Overlapping Subproblems:

Dynamic programming is mainly used when solutions of the same subproblems are needed again and again. So Dynamic Programming is not useful when there are no common (overlapping) subproblems because there is no point in storing the solutions if they are not needed again.

For example, Binary Search doesn’t have common subproblems. If we take an example of following the recursive program for Fibonacci Numbers, there are many subproblems that are solved again and again.

Recursion tree for the execution of fib(5):

                         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(0)

We can see that the function fib(3) is being called 2 times. If we would have stored the value of fib(3), then instead of computing it again, we could have reused the old stored value.

Optimal Substructure:

A given problem has Optimal Substructure Property if an optimal solution of the given problem can be obtained by using optimal solutions of its subproblems.

For example, the Shortest Path problem has the following optimal substructure property:

If a node x lies in the shortest path from a source node u to destination node v then the shortest path from u to v is a combination of the shortest path from u to x and shortest path from x to v. The standard All Pair Shortest Path algorithms like Floyd–Warshall and Bellman-Ford are typical examples of Dynamic Programming.

On the other hand, the Longest Path problem doesn’t have the Optimal Substructure property.

---

Happy Coding!

Follow us on Instagram @programmersdoor

Join us on Telegram @programmersdoor

Please write comments if you find any bug in the above code/algorithm, or find other ways to solve the same problem.

Follow Programmers Door for more.

#blog #interview #placement #learn #computer #science