Dynamic Programming

CORE DEFINITION

Dynamic programming (DP) is a method used in mathematics, management science, computer science, economics, and bioinformatics to solve complex problems by breaking them down into simpler subproblems. It is applicable to problems with overlapping subproblems and optimal substructure properties, and often consumes far less time than naive solutions. The basic idea behind dynamic programming is very simple. In general, to solve a given problem, we need to solve its different parts (i.e., subproblems), and then combine the solutions of the subproblems to reach an overall solution. Often many of these subproblems are very similar, so dynamic programming attempts to solve each subproblem only once, thereby reducing the amount of computation: once the solution to a given subproblem has been computed, it is stored (memoized) so that the next time the same solution is needed, it can simply be looked up. This approach is particularly useful when the number of repeating subproblems grows exponentially as a function of the size of the input.