# properties of dynamic programming

1)Overlapping Subproblem Property

2)Optimal Substructure Property

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:

lets take a example : n=4

####

####

####

####

####

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

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)**

**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

this is an example for overlapping subproblem

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

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.

https://codemummy.blogspot.com/2020/08/0-1-knapsack-problem.html

**time complexity**of the above dynamic approach is linearthis 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