A Dynamic programming problem has a optimal substructure.
The second most important truth of DP!
What does this mean? It simply means that you cannot apply DP unless you are sure that the optimal solution of sub-problems will help you in getting the optimal solution of the bigger problem. And how would any sane person know if a problem has optimal sub-structure? Simple, by putting your grey cells to work.
What does this mean? It simply means that you cannot apply DP unless you are sure that the optimal solution of sub-problems will help you in getting the optimal solution of the bigger problem. And how would any sane person know if a problem has optimal sub-structure? Simple, by putting your grey cells to work.
Lets think about it taking a example.
- Shortest Path
The problem is to find a shortest path from a vertex u to vertex v in a graph G (lets forget about the nature of the graph for a while ... I am trying to lay out a concept).
The problem is to find a shortest path from a vertex u to vertex v in a graph G (lets forget about the nature of the graph for a while ... I am trying to lay out a concept).
Lets say we have i vertices (labelled from 1,2,3 .. i) from u to v in the actual shortest path. So the shortest path looks like this:
u ->1 -> 2 -> 3 -> .... ->i -> v
Now to reach vertex v through a shortest path, you must reach vertex i through the shortest path. Why? Because if you do not do so, and give me a solution that includes a path from u to v through i such that the path from u to i is not the shortest one, then I will simply replace the path from u to i with the shortest path and get a better solution than the one you gave to me!
Whoa! Do you see now the meaning of optimal sub-structure. You cannot solve shortest path from u to v optimally unless you solve shortest path from u to i optimally. And you cannot solve the shortest path from u to i optimally unless you solve the shortest path from u to j (where j is an intermediate vertex in the shortest path from u to i). And you cannot solve shortest path from u to j unless ... the story continues.
At this juncture, I hope you might be a little sensitive to DP and its truths. But a few of you might be stricken by the feeling that this all seems so dreadfully familiar to Divide and Conquer technique. Yes, indeed. This is similar, but yet different. The next part is the grand finale for the DP treatise where I will outline a few more insights into it. Till then, an interesting fact to ponder about:
Solving single source shortest path to a destination vertex in a graph is as hard as solving single source shortest path to all the vertices. Think about it, have you seen a polynomial time algorithm that calculates the single source single destination shortest path only without calculating all other shortest paths from the source?
Voila! This is your chance to fame. :)
Solving single source shortest path to a destination vertex in a graph is as hard as solving single source shortest path to all the vertices. Think about it, have you seen a polynomial time algorithm that calculates the single source single destination shortest path only without calculating all other shortest paths from the source?
Voila! This is your chance to fame. :)
Nice blog Nikhil. Love your explanations! Keep it up.
ReplyDelete