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

darkmode