Skip to main content

Dynamic Programming

Basic concept#

One of the most feared topics of competitive programming but also one of the most interesting and useful. Optimizing the time complexity of your code can sometimes be the most challenging task at hand. Using Dynamic Programming you can optimise the time complexity of your code, in some cases you can even reduce from an exponential time complexity to polynomial time complexity. So how does dynamic programming help you in optimisation of your code? What are the trade offs? When, where and how to apply dynamic programming? If these are the questions that come to your mind, then do not worry, you are at the correct place, all your queries will be answered, read and learn from these wonderful articles. It is recommended that you go through each till the end.

Caution

Before applying Dynamic Programming to a problem start with discovering the choices that you can make that will take you from one definite state to another, then you must define and give a meaningful definition to your dp state, next form a relation between your current dp state and the previously visited dp states. Sometimes these choices are clearly given in a problem, but sometimes they are hidden and you have to figure out the choices that you can make.

State Space Reduction#

Dynamic Programming is an optimisation technique, but there is a second level optimisation to dynamic programming as well and it is called state space reduction where you eliminate the unnecessary elements from your dp state. Usually such elements can be dropped because their value can be calculated from the other state elements. Constraints on a problem can be tough sometimes so adding unnecessary elements to your dp state will give you a TLE, to avoid it you must continue reading to know about it.

Practice and learn#

It is important that you go through our practice and learn section thoroughly to get a good grasp of the concept of DP applied to different patterns of problems and scenarios.

Questions#

1D/2D#

String DP#

Tree DP#

Random#