Dynamic Programming

Here is a quick introduction to the dynamic programming paradigm.

We'll cover the following

What is dynamic programming?

Dynamic programming algorithms solve problems by combining results of subproblems— just like divide and conquer algorithms.

“Those who cannot remember the past are condemned to repeat it.” – Dynamic Programming

Characteristics

  1. Overlapping Subproblems: the subproblems of a given problem are not independent. In other words, two subproblems share a problem.

  2. Optimal Substructure Property: the overall optimal solution of the problem can be constructed from the optimal solutions of its subproblems.

Dynamic programming patterns

There are two approaches which come in handy when a problem is to be solved using dynamic programming:

Memoization (top-down)

The memoized version of a problem is similar to the regular recursive version, except that it looks for the answer of a subproblem in a lookup table before computing its solution.

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.