The 8 Robot Masters of Learning Dynamic Programming

*This article is based on my journey going through this video. I highly recommend it for learning Dynamic Programming.

Dynamic Programming IS HARD!! It is a rather advanced topic and requires you to leverage a lot of knowledge to really be able to wield it effectively. It is also not a very intuitive subject to learn without some form of prior exposure to it. And it comes up in interview questions quite often so it's a must learn subject for practicing for interviews. There have been talks of some large tech companies removing them from their question pool but for now it’s best to assume that you’ll run into one if you’re interviewing at a large tech company. For those who don’t know what Dynamic Programming is, it’s a set of optimization techniques that you can use on problems where you can break the problem down to subproblems and then combine their solutions to get the solution you want.

So in my attempt to learn this topic (which has been successful mainly because of the video I linked at the beginning of this article), there are 8 questions that if you can answer optimally and describe the space and time complexity will give you a strong base to answer DP questions:

1. Fibonacci Sequence
2. Grid Traveler
3. canSum
4. howSum
5. bestSum
6. canConstruct
7. countConstruct
8. allConstruct

Full disclosure, the video I linked teaches you DP by walking you through these problems’ solutions.

So these problems have a general progression to them in terms of what you need to know in order to complete them. The first few problems, while they do help solidify DP concepts, are very much their own entities where the last few are really the same problem with changes to the goal to increase the problem’s difficulty.

Fibonacci Sequence

“Write a function ‘fib(n)’ that takes in a number as an argument. The function should return the n-th number of the fibonacci sequence.

The first and second number of the sequence is 1. To generate the next number of the sequence, we sum the previous two.”

This is THE classic DP problem. The brute force implementation of this problem is fairly easy as you just need to know how to implement the fibonacci sequence to do it. It gets difficult when you realize that larger fib numbers can take forever to calculate using the brute force solution. This is when you try to implement a solution to decrease the time by using techniques like memoization and tabulation. Overall, I think this is actually a great problem to introduce people to things like the importance of time complexity and trading space complexity for it and then the DP techniques themselves. Personally, I found that I could implement the optimal solution for the fibonacci sequence but I could not translate that knowledge to other DP questions as well and so I’d caution on doing only this problem and suddenly feeling comfortable with DP.

Grid Traveler

“Say that you are a traveler on a 2D grid. You begin in the top-left corner and your goal is to travel to the bottom-right corner. You may only move down or right.

In how many ways can you travel to the goal on a grid with dimensions m * n?

Write a function 'gridTraveler(m, n)' that calculates this.”

So this question is where all your confidence in DP gets thrown out the window from fibonacci (at least that’s how it was like for me). So what makes this question so much more different than the fibonacci sequence is that in that problem, the relationship was simply given to you. A big part of DP is actually accurately coming up with good relationships to the various sub problems you need to solve to get the solution period, much less optimize it. Here the sequence is hidden in the text of the problem statement and because it’s a grid, you immediately think of some form of graph traversal. So this problem teaches you the skill of finding the relationship between the subproblems becomes invaluable and is the key to solving DP problems moving forward.

canSum

“Write a function 'canSum(targetSum, numbers)' that takes in a targetSum and an array of numbers as arguments.

The function should return a boolean indicating whether or not it is possible to generate the targetSum using numbers from the array.

You may use an element of the array as many times as needed.

You may assume that all input numbers are nonnegative.”

This is where things become more structured and the degree of difficulty changes from being “Oh my God, I can’t do this!!” to “Okay, how do I stretch my current knowledge to get to the output the problem statement wants?” The thing that’s added here is that before, the potential moves you can take were static. Now the moves you can take are dynamic and you have to take that into account. It is actually not that much different from the previous two problems solved but now taking in a dynamic amount of moves really stretches you. I haven’t been talking about it but this is also where your understanding of space time complexity also gets stretched depending on the implementation of your solution. It becomes somewhat tricky to discern the correct space time complexity depending on your implementation.

howSum

“Write a function 'howSum(targetSum, numbers)' that takes in a targetSum and an array of numbers as arguments.

The function should return an array containing any combination of elements that add up to exactly the targetSum. If there is no combination that adds up to the targetSum, then return null.

Neither targetSum or numbers in the array can be negative.”

So where canSum forces you to think of a dynamic selection of moves and leverage that to solve the problem, howSum says “alright, you can solve the problem but give me the solution.” In the previous problem, you didn’t need to track the solution, you just need to prove that the solution existed or not. In this problem, it wants you to show a potential solution if it exists. It’s not that much more difficult from canSum but there are some considerations that need to be made to ensure you output a good solution. I view it as forcing you to output a ‘complex’ data structure and so you need to construct the data structure as you are going through your algorithm to output it.

bestSum

“Write a function 'bestSum(targetSum, numbers)' that takes in a targetSum and an array as arguments.

The function should return an array containing the shortest combination of numbers that add up to exactly the targetSum.

If there is a tie for the shortest combination, you may return any of the shortest.”

So where howSum asks you to deliver any single solution, bestSum asks you to deliver the absolute best solution based on criteria. The implementation isn’t that much more difficult than the previous two solutions but now you have to consider how you’re going to decide on how to keep the best solution possible.

canConstruct

“Write a function 'canConstruct(target, wordBank)' that accepts a target string and an array of strings.

The function should return a boolean indicating whether or not the 'target' can be constructed by concatenating elements of the 'wordBank' array.

You may resume elements of 'wordBank' as many times as needed.”

This problem is very similar to canSum but the big difference here is the data type of the input you need to use. You now need to use strings instead of just primitives which makes the problem harder to work with. Essentially, it tests your knowledge of DP while also exercising your ability to manipulate strings. The solution is actually pretty similar to canSum but if you look at them side-by-side, the difference is actually between how you manipulate strings so as long as you keep that in mind, the problem should feel less scary if you’ve done canSum successfully.

countConstruct

“Write a function 'countConstruct(target, wordBank)' that accepts a target string and an array of strings.

The function should return the number of ways that the 'target' can be constructed by concatenating elements of the 'wordBank' array.

You may reuse elements of 'wordBank' as many times as needed.”

So this problem shifts a little bit away from the others I describe by telling you to count all the different ways you can construct a string. So what makes this problem a bit more interesting is that it’s a lot closer to bestSum than howSum as it forces you to go through the entire list of in the array and come up with every single solution. This problem still allows you to output primitives which is great but you are stretched a bit having to consider the entirety of the array.

allConstruct

“Write a function 'allConstruct(target, wordBank)' that accepts a target string and an array of strings.

The function should return a 2D array containing all the ways that the 'target' can be constructed by concatenating elements of the 'wordBank' array. Each Element of the 2D array should represent one combination that constructs the 'target'.

You may reuse elements of the 'wordBank' as many times as needed.”

This, in my opinion, is the hardest DP problem I’ve ever seen. So it follows the same progression that you’ve seen in the other problems but now you have to take a complex data structure (i.e. strings) and output a complex data structure (i.e. a 2D array) and it has to be in a particular structure to complete the task successfully. I personally have completed this problem but it took me A WHILE to wrap my head around the solution and ultimately I needed help to solve it. I plan on going back to this problem again in a few days to try and solve it on my own again. I feel this question encapsulates all the lessons you learned about DP on the way to this problem and really helps solidify them in your mind. If you can solve this problem AT ALL, pat yourself on the back and you deserve a cookie.

And there you have it! These are the 8 Robot Masters of learning Dynamic Programming!

My Thoughts

Dynamic Programming is a frustrating topic because it’s so difficult to learn and it’s so rarely used by Engineers in the field (cue someone dropping into the comments on the problem they had that they solved using DP). My experience with DP is… well I honestly liked learning this topic and while I doubt I’ll ever use it in the field, I would love to write production code using these techniques. Otherwise, I think these problems make for a great Code Kata or a fun little practice thing especially with other Engineers.

Now in terms of as an interview question? I think they’re overkill. I’m not sure if I would consider someone who could demonstrate they could do DP problems to be an exceptional Engineer. I mean I can do DP problems now and I don’t consider myself an exceptional Engineer AT ALL (gotta get my self deprecation quota in). While removing it from the question pool entirely won’t suddenly solve the issues people have with big tech interviews, it’ll definitely reduce the headache of having to learn this topic just to try and pass these interviews (I failed a big tech interview because of a DP problem. Damn you Coin Change!).

So I hope this article was at least interesting or informative. I feel like going through these problems separately in a similar order they were given here would go a long way in helping you learn this very difficult topic. With that, happy coding!!