Dynamic Programming | Set 2 (Optimal Substructure Property) | GeeksforGeeks

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.


Leave a Reply

Your email address will not be published. Required fields are marked *