Hello friends! Welcome to GeeksforGeeks. In this video, we will discuss the Optimal

Substructure property of Dynamic Programming problems. We say that a given problem has the Optimal

Substructure property if the problem can be solved optimally by using the optimal solutions

of its subproblems. The Dynamic Programming techniques exploit

this property to split the problems into smaller subproblems and solve them instead. This is useful because after the subproblems

become sufficiently small, solving them becomes trivial. These trivial solutions can then be used to

solve the super-problems and arrive at the final result. Let’s take the example of the Shortest Path

problem. The problem says that we are given a graph

and we are required to find the shortest path from source vertex u to destination vertex

v. Say that, x is a vertex that lies on the shortest path from u to v. Then, the path

from u to x has to be the shortest path from u to x. Similarly, the path from x to v has to be

the shortest from x to v. So, we see that the Shortest Path problem can be optimally

solved by using optimal solutions of subproblems. In fact, the standard All Pair Shortest Path

algorithms like Floyd-Warshall and Bellman-Ford are typical examples of Dynamic Programming

problems. Let’s now take a counterexample. Consider the Longest Path problem. Given a graph, it requires us to find the

longest path (without any cycle) from a source vertex u to a destination vertex v.

Consider the shown unweighted directed graph. There are two longest paths from q to t: q→r→t

and q→s→t. However, the longest path from q to t (q→r→t)

is not a combination of the longest path from q to r (q→s→t→r) and the longest path

from r to t (r→q→s→t) as this combination contains a cycle. So, we see that the Longest Path problem is

not an example of Dynamic Programming problems. That’s all for now. Thank you for watching.

## 7 Comments

## Bibhuti Bhusan Panda

Videos are good but I think this video which shows itself in index 4 of playlist should show itself at index 2

## ziiip

Nice, cheers.

## Abhijeet Rawat

I have finally understood a bit about dynamic programming , a million thanks brother !

## vedavyas R.V.S.S

bro… everything is fine why dont u talk a bit loud. i need to wear earphones because of ur low voice 🙁

## Montana 2

thank you for these videos, really makes it more simple.

## Enrique Jaimes

Thank god for the subtitles, appreciated.

## VoodooD0g

this should be a playlist or at least linked in the description 🙁