Dynamic Programming

Dynamic programming is a very widely used technique. You may have even been applying it without knowing it. Its applications vary from very simple ones to more complicated cases. Nevertheless, many people wonder if they even need that for the interviews. Our experience shows that it is likely that you would get a problem requiring you to design a solution using dynamic programming. Overall, it is useful knowledge for many software engineers. Depending on what you work on it can come very handy sometimes.

How to proceed with this section?

There are plenty of articles and books out there covering the topic very thoroughly. If you are new to dynamic programming our advice is to read these overview lessons and then go through some more in depth articles available online. We will offer useful links at the end of this lesson. Once you feel confident with your knowledge about dynamic programming you should continue to the practice tasks.

About dynamic programming

So, what is dynamic programming? In short, it’s a method, which allows you to solve a problem by breaking it down into smaller sub-problems. With dynamic programming you will try to identify a way to combine the answers for smaller versions of a problem to compute the answer for a bigger version. If you find such a recurrent dependency you would be able to start with some very trivial cases, which you know the answer to, and subsequently compute the answers of bigger and bigger versions of the problem until you reach the version that you were initially interested in.

The above method works well if you store the answers for smaller versions of the problem and reuse the computed values when computing for bigger versions of the problem. This technique is called “memoization”.

Resources