Python Data Structures and Algorithms

Dynamic programming

This technique is similar to divide and conquer, in that a problem is broken down into smaller problems. In divide and conquer, each subproblem has to be solved before its results can be used to solve bigger problems. By contrast, dynamic programming does not compute the solution to an already encountered subproblem. Rather, it uses a remembering technique to avoid the recomputation.

Dynamic programming problems have two characteristics: optimal substructure and overlapping subproblem. We will talk more on this in the next section.