Dynamic programming is an optimization strategy for designing algorithms. The technique is beneficial for technical interviews because solving problems with an optimal big O runtime will improve your chances of being hired.

We’ll describe dynamic programming with a question: What is 1 + 1 + 1 + 1?

Now, what is one more, or 1 + 1 + 1 + 1 + 1?

For the first question, you counted each 1 to arrive at 4, but for the second question, you only needed to add 1 to the previous total. You “stored” the previous sum to avoid a calculation already performed.

That’s dynamic programming! Break a problem into smaller sub-problems, store the answers to the sub-problems, and use those stored answers to solve the original problem.

We need overlapping sub-problems for the stored answers to be useful; answers for overlapping sub-problems are consistent and relevant to the original problem.

With a linear search, we examine each element in a collection to find a target element. We can’t apply dynamic programming because there is no overlapping sub-problem. An element’s location can vary between searches and the location in one search has no relevance to another search in a larger collection.