Dynamic Programming: Advanced
Interview Essentials
Dynamic programming is a powerful technique that helps you solve complex problems by breaking them down into simpler recurring subproblems. This is generally done by taking a recursive algorithm and finding the repeated calls, the results of which you can then store for future recursive calls. Since you've compute the answer for an input and saved it for later, you don’t have to recompute it the next time around!
In technical interviews, dynamic programming is especially useful when you’re solving problems about optimization, search, and counting. If, as you're analyzing a problem, you see that it can be broken down into smaller overlapping subproblems, it's a good signal that you can employ dynamic programming to solve it.
Important Concepts
There are two common dynamic programming strategies that you'll need to familiarize yourself with, bottom-up and top-down.
Bottom-up strategy (iteration): In this strategy, you start solving from the smallest subproblem up towards the original problem. If you’re doing this, you’ll solve all of the subproblems, thereby solving the larger problem. The cache in bottom-up solutions is usually an array (either one or multi-dimensional).
Top-down strategy (recursion): Start solving the identified subproblems. If a subproblem hasn’t been solved yet, solve it and cache the answer; if it has been solved, return the cached answer. This is called memoization. The cache in top-down solutions is usually a hash table, binary search tree, or other dynamic data structure.
Generalized Algorithm
Find a recursive or iterative solution to the problem first (although usually these will have bad run times).
This helps you identify the subproblems, which are “smaller” instances of the original problem.
Determine whether the subproblems are overlapping. If they’re overlapping, a recursive algorithm will be solving the same subproblem over and over. (If they’re not overlapping and the recursive algorithm generates new subproblems each time it runs, DP isn’t a good solution; try a divide-and-conquer solution like merge sort or quick sort instead.)
Store/cache the results for every subproblem.
Once the subproblems have solutions, the original problem is easy to solve!
In Interviews, Expect to See Problems Like...
Knapsack problems
Scheduling problems
Compute the
nth Fibonacci number
Last updated