Dynamic programming – optimal sub-structure

In THIS post, we covered the overlapping sub-problems part of dynamic programming. Now we will talk about what do we mean by “optimal sub-structure”?

Assume we have a graph like below. What is the shortest path from node A to node D? It is A->C->D. So, optimal structure property means that if a node (C) lies between the shortest path of two nodes (A and D) then the shortest path between the two nodes (A and D) will be the shortest path between the source node (A) to the intermediary node (C) plus the shortest path from the intermediary node (C) to the destination node (D). Note that if we were to find the longest path between two nodes then this property does not hold true (try drawing out a graph and see for yourself why?)

Fig. 1. Shortest path problem holds optimal sub-structure property of dynamic programming

In the next few posts, we are going to solve a few DP questions to understand our concepts better.

References:

1. GeeksforGeeks 2017. “Dynamic Programming | Set 2 (Optimal Substructure Property)”. https://www.geeksforgeeks.org/dynamic-programming-set-2-optimal-substructure-property/. [Online; accessed 14-Jan-2018].