Dynamic Programming - Introduction

 
What is Dynamic Programming?
  • Dynamic Programming or DP is a method for solving a problem by breaking it into smaller sub-problems, solving the subproblems only once and storing the result of the sub-problems for future use so that we do not solve a sub-problem again and again (like we do in Divide and Conquer).
  • Dynamic Programming is just an optimization of Divide and Conquer. In Divide and Conquer we may solve sub-problem multiple times, but DP prevents that by storing the result of a sub-problem once it is solved once, thus saving on run-time and compromising a little on space complexity.
When Should we use the Dynamic Programming approach?
When we see these both of these properties in a problem, we can use DP:
  • Optimal Substructure 
  • Overlapping Subproblems
    • Any problem has overlapping sub-problems if finding its solution involves solving the same sub-problems multiple times.
    • This property is unique for Dynamic Problem.

Two Types of Dynamic Programming Approach
1. Top-Down Approach (Memoization)
  • In this approach of Dynamic Problem, the problem is first broken into sub-problems. Then these sub-problems are solved.
  • The solution to these sub-problems is remembered so that we can use it in the future if needed.
  • This is simply the extension of Dynamic Programming.
  • Example:
        Let's consider we have to find Fibonacci of (4).
        1. We break fib(4) = fib(3) + fib(2)
        2. Then we break fib(3) = fib(2) + fib(1) whose value we know as 1 and 0 respectively.
        Here, We know the values of fib(1) = 0 and fib(2) = 1 [base cases]. We have already got it stored somewhere. So, when we get to the recursive call of fib(3) it picks the value of fib(1) and fib(2) directly add it and return the value of fib(3).
        3. Now. we reach step 2 again (by recursion). Here instead of now calling fib(2) again, we use its value from memory and return the final value of fib(4).

So, what we are doing here is we are first breaking a given problem into smaller subproblems, solving individual sub-problems once and storing its result, and then combining result of these subproblems to get the solution of bigger subproblem and eventually get the solution to the whole problem.

2. Bottom-Up Approach (Tabulation)
  • In this approach, instead of breaking the problem into sub-problems recursively, we evaluate the function starting with the smallest possible input argument value and then moving to the larger input value. 
  • Here we go from solving the smallest problem possible to eventually solving the main problem. But remember, we DO NOT BREAK A PROBLEM INTO SUBPROBLEMS
  • While computing the values we store all the computed values in memory(table).
  • As larger input arguments are evaluated, pre-computed values for smaller arguments can be reused.
  • In this case, all the subproblems that we might need in future are precompiled and then they are used to solve bigger problems.
  • Example:
            Let's consider the same example as above, that is, finding Fibonacci(4)
            1. We first try to find fib(1), which we already store in our memory as base case along with fib(2) which is 1.
             2. Now, we go on to find fib(2) => which we get from our memory
             3. Now, we go on to find fib(3) = fib(2) + fib(1), which we find using already stored values of fib(2) and fib(1) and adding them. We then save the result of fib(3) in memory.
             4. Now, we go on to find fib(4) = fib(3) + fib(2), both of which can be found in our memory, so no computation needed. 

So, what we are doing here is we are starting from solving smallest possible chunk and eventually go on to solve bigger chunks using these pre-computed values of smaller chunks.

Comparing Fibonacci Number problem's Time complexity 
         Problem          Divide and Conquer       Top-Down DP         Bottom-Up DP   
     Fibonacci Number     Exponential (O(1.61)^n) O(n) O(n) 


Top-Down Approach vs Bottom-Up Approach
   
   Comparision Factor     		    Top-Down Approach         Bottom-Up Approach    
 Ease of Algorithm
Easy to come up with a solution
as it is an extension of Divide
and Conquer.
 Not so easy to come up with
a solution.
 Run-Time
 Relatively slower as it is an 
 Recursive approach.
 Relatively faster as it is an Iterative
 approach.
 Space
 The internal stack is used because of
 recursion
 No internal stack is used as it is 
 iterative.
 When to use  When a quick solution is needed  When a more efficient solution is      needed
 
 
Famous Problems (relevant to coding interview) that can be solved using Dynamic Programming
Important Note: I would highly recommend solving these problems. These are common and are mostly asked problems, which will also help us to gain an understanding of Dynamic Programming. To really understand Dynamic Programming, we should emphasize more on practicing its questions. For now, we can start with these:


1. Fibonacci Series
2. Number Factors / Coin Change Problem
3. House Robber
4. Minimum Edit Distance problem
5. Longest Common Subsequence 
6. Longest Palindromic Subsequence
7. Longest Palindromic Substring
8. Min Cost to reach the last cell (bottom-right) from the first cell (top-left) in a 2D array
9. Number of possible paths from the first cell (top-left) to the last cell (bottom-right) in a 2D array



Comments

Post a Comment

Popular posts from this blog

Binary Heap - Introduction

Image
#Image Credit - GeeksForGeeks Types of heap: Min Heap - every node is less than or equal to  its children(s) Max Heap - every node is more than or equal to its children(s) Operations on any heap : create insert extract/delete - we can extract/delete only the top node in any heap traverse delete entire heap get size of heap peek top of heap We should prefer implementing binary heap using arrays and not linked list, as during bottom to top heapify, in reaching the bottom rightmost node we take only 0(1) time in case of array but we take 0(n) time in case of linked list because first, we need to level order traverse the binary heap tree to get bottom-most rightmost element.  Heaps are used to efficiently implement:  Prim's Algorithm Heapsort Priority queue
Read more

Divide and Conquer - Introduction

Image
What is Divide and Conquer? Divide and Conquer is an algorithm paradigm in which we break down a given problem into smaller sub-problems of similar type until the sub-problems are small enough to be solved directly. The solution to these sub-problems are then combined to give a solution to the original problem.  Study the diagram below, it will then make more sense about what we do in Divide and Conquer : Where to Apply Divide and Conquer? The Divide and Conquer can be applied to all those problems that show Optimal Substructure property.  So, What is this Optimal Substructure property now? If we can break down a problem into similar sub-problems and the solution of these sub-problems can be used to create the solution of the whole problem, then that problem is said to have the Optimal Substructure property. For eg. : Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2),    In this example, we can see that if we want to find the Fibonacci number at the nth place, we can br...
Read more

Bubble Sort

Time complexity - O(n^2)  || Space Complexity - O(1) Bubble sort is an inplace sorting algorithm, that means we do not any extra space while bubble sorting public class Main {     public static void main(String[] args) throws Exception {         int[] arr={1,4,4,5,6,2,3,90,120,43,0};                  System.out.println("UnSorted Array :");         for(int i=0;i<arr.length;i++){             System.out.print(arr[i]+" ");         }         System.out.println();         // bubble sort         for(int i=0;i<arr.length-1;i++){ // iterates through first to last cell             for(int j=0;j<arr.length-1-i;j++){ // inner loop controls swapping and extent to which swapping is to be performed in array     ...
Read more