Data Structures and Algorithms · Techniques

Dynamic programming

Solving a problem by caching answers to overlapping subproblems instead of recomputing them.

Also known as: DP, memoization, tabulation, overlapping subproblems.

Start a lesson on Dynamic programming

Learn first

• Divide and conquer: Splitting a problem into independent smaller copies of itself, solving each, then combining.

Related topics

• Greedy algorithms: Making the locally best choice at every step and trusting it leads to a globally best answer.
• Recursion: A function solving a problem by calling itself on a smaller version of the same problem.