properties of dynamic programming

1)Overlapping Subproblem Property
2)Optimal Substructure Property


1)Overlapping Subproblem Property:

A problem has overlapping subproblems if finding its solution involves solving the same subproblem multiple times.

consider the example of calculating nth fibonacci number:

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

the recursive solution of the above is:

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

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



lets take a example : n=4

                  fib(4)                                                      

                /           \                                          

          fib(3)          fib(2)        

        /        \             /        \                   

    fib(2)   fib(1)    fib(1) fib(0)   

     /    \

fib(1) fib(0)

as u can c fib(2),fib(1),fib(0) are calculated more times , if n was larger than we had to repeat the process many times the time complexity is exponential,instead we can use dynamic programming


int fib(int n) 
{ 
  // Declare an array to store Fibonacci numbers
  int f[n+2];   // 1 extra to handle case, n = 0 
  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++) 
  { 
      // Add the previous 2 numbers in the series 
      // and store it 
      f[i] = f[i-1] + f[i-2]; 
  } 
  
  return f[n]; 
}

here we are reusing the previously stored value

the time complexity of the above dynamic approach is linear
this is an example for overlapping subproblem


2)Optimal Substructure Property:

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

lets take an example:

there are three houses a,b,c
b lies in between a and c
if the shortest distance between a and c is the combination of the shortest distance between a and b  and shortest distance between b and c than it is a optimal substructure problem


consider the 0/1 knapsack problem it can be solved using Optimal Substructure .

in which there can be two cases for every item: (1) the item is included in the optimal subset, (2) not included in the optimal set.


to see the  0/1 knapsack problem solution click on this link
https://codemummy.blogspot.com/2020/08/0-1-knapsack-problem.html