Dynamic Programming - Introduction
What is Dynamic Programming? Dynamic Programming or DP is a method for solving a problem by breaking it into smaller sub-problems, solving the subproblems only once and storing the result of the sub-problems for future use so that we do not solve a sub-problem again and again (like we do in Divide and Conquer). Dynamic Programming is just an optimization of Divide and Conquer. In Divide and Conquer we may solve sub-problem multiple times, but DP prevents that by storing the result of a sub-problem once it is solved once, thus saving on run-time and compromising a little on space complexity. When Should we use the Dynamic Programming approach? When we see these both of these properties in a problem, we can use DP: Optimal Substructure This property has already been explained in the post of Divide and Conquer , as Divide and Conquer also have this property. Overlapping Subproblems Any problem has overlapping sub-problems if finding its solution involves solving the same sub-...